HDU4909 String

题目

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

[Technical Specification]

  1. 1 <= N <= 40000
  2. 1 <= M <= N

Output

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

Simple input

3
abc?ca
aabbcc
aaaaa

Simple output

7
6
6

题目分析

这个题目和4908的情况差不多,不过要对?的两侧进行搜索,并且采用了壮压

AC代码

3608K/1248MS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
void fre()
{

freopen("c://test//input.in", "r", stdin);
freopen("c://test//output.out", "w", stdout);
}
#define MP(x,y) make_pair(x,y)
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
#define debug puts("----------")
#define INF 0x3f3f3f3f
#define maxn 1050
const long long mod = 1e9+7;
using namespace std;
char str[20005];
int st[20005];
map<int,int>lef;
map<int,int>rig;
map<int,int>mp;
int main()
{

int T;
scanf("%d",&T);
while(T--)
{
lef.clear();
rig.clear();
mp.clear();
scanf("%s",str+1);
int l = strlen(str+1);
int pos = 0;
for(int i=0; i<=l; i++)
{
if(str[i]=='?')
{
pos = i;
st[i]=st[i-1];
}
else
{
//printf("%d====\n",st[i]);
st[i] = (st[i-1]^(1<<(str[i]-'a')));
cout<<((1<<(str[i]-'a')))<<endl;

}
}
for(int i=0; i<=l; i++)
{
mp[st[i]]++;
if(pos && i<pos)
{
lef[st[i]]++;
}
if(pos && i>=pos)
{
rig[st[i]]++;
}
}
int ans=0;
if(pos)
{
for(map<int,int>::iterator it = lef.begin(); it!=lef.end(); it++)
{
int x = it->first;
for(int j = 0; j < 26; j++)
{
int y = (x^(1<<j));
map<int,int>::iterator ct = rig.find(y);
if(ct!=rig.end())
{
ans+=(it->second)*(ct->second);
}
}
}
}
for(map<int,int>::iterator it = mp.begin(); it!=mp.end(); it++)
{
ans+=(it->second*(it->second-1))/2;
}
printf("%d\n",ans);
}
}

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4909