HDU 4909

String

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 54 Accepted Submission(s): 13

Problem Description

You hava a non-empty string which consists of lowercase English letters and may contain at most one ‘?’. Let’s choose non-empty substring G from S (it can be G = S). A substring of a string is a continuous subsequence of the string. if G contains ‘?’ then ‘?’ can be deleted or replaced by one of lowercase english letters. After that if each letter occurs even number of times in G then G is a good substring. Find number of all good substrings.

Input

The input consists of an integer T, followed by T lines, each containing a non-empty string. The length of the string doesn’t exceed 20000. [Technical Specification] 1 <= T <= 100

Output

For each test case, print a single integer which is the number of good substrings of a given string.

Sample Input

3 abc?ca aabbcc aaaaa

Sample Output

7 6 6

Hint

Good substrings of “abc?ca”: “?”, “c?”, “?c”, “c?c”, “bc?c”, “c?ca”, “abc?ca”

Source

BestCoder Round #3

因为最多只有一个?   两段可以的话，字母出现次数的奇偶性只能相等或者差1\. 用map 去映射出现次数，然后查找。   一个坑点导致了TLE, 还是对map 不够熟悉啊。 如果直接ans += mp\[s\],  会新加入好多无用点，s如果不在会直接插入的。 应该if(mp.count(s))ans += mp\[s\];

/* ***
Author :kuangbin
Created Time :2014/8/3 19:47:05
File Name :C.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
int num[30];
char str[20010];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
scanf(“%d”,&T);
while(T–)
{
scanf(“%s”,str);
map<int,int>mp1;
map<int,int>mp2;
bool has = false;
int n = strlen(str);
has = false;
mp1[0]++;
memset(num,0,sizeof(num));
int s = 0;
int ans = 0;
for(int i = 0;i < n;i++)
{
if(str[i] != ‘?’)
{
s ^= (1<<(str[i]-‘a’));
}
else
{
has = true;
}
if(!has)
{
if(mp1.count(s))ans += mp1[s];
mp1[s]++;
}
else
{
if(mp2.count(s))ans += mp2[s];
if(mp1.count(s))ans += mp1[s];
for(int j = 0;j < 26;j++)
if(mp1.count(s^(1<<j)))
ans += mp1[s^(1<<j)];
mp2[s]++;
}
}
printf(“%d\n”,ans);
}
return 0;
}

可以使用数组进行优化，空间换时间。

/* ***
Author :kuangbin
Created Time :2014/8/3 19:47:05
File Name :C.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
char str[20010];
short num1[1<<26];
short num2[1<<26];
int a[20010];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
scanf(“%d”,&T);
while(T–)
{
scanf(“%s”,str);
bool has = false;
int n = strlen(str);
num1[0]++;
int s = 0;
int ans = 0;
for(int i = 0;i < n;i++)
{
if(str[i] != ‘?’)
{
s ^= (1<<(str[i]-‘a’));
}
else
{
has = true;
}
a[i] = s;
if(!has)
{
ans += num1[s];
num1[s]++;
}
else
{
ans += num1[s];
ans += num2[s];
for(int j = 0;j < 26;j++)
ans += num1[s^(1<<j)];
num2[s]++;
}
}
for(int i = 0;i < n;i++)
{
if(num1[a[i]])num1[a[i]] = 0;
if(num2[a[i]])num2[a[i]] = 0;
}
num1[0] = 0;
printf(“%d\n”,ans);
}
return 0;
}