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