http://www.spoj.com/problems/STC02/en/
题意：给出一个长度为n的字符串，问其中有多少个子串s可以使得s = s按位取反+翻转。
例如样例：11001011.
10可以，因为取反 = 01，翻转 = 10. 所以算一个。
思路：可以看成是回文串，使用Manacher算法求解。
当向两边扩张的时候，判定条件修改成左边是1或者0，右边就是0或者1，或者都是#。
因为那个子串一定是偶数长度，刚好就是s[i] = '#'的时候就更新答案，该位置的回文串对答案的贡献就是本身不包含'#’的长度，因此是p[i] / 2.
有一个点WA了很久。就是只有s[i] = '#'的时候才可以更新mx。为什么要这样呢？
看这个样例就明白了：011
变成：$#0#1#1#
如果不加判定条件的话，扫到第一个1的时候，p[4] = 4，这个时候mx会更新到右端点。
那么等到p[5]的时候，就会变成p[5] = 3，因为执行了 if(mx > i) p[i] = min(p[id*2-i], mx - i); 这个语句。
但是事实上p[5]是不能向外扩张的，p[5] = 1。
还是需要多考虑细节上的问题啊。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 500010 4 int p[N*2]; 5 char str[N], s[N*2]; 6 7 bool check(char c1, char c2) { 8 if(c1 == '1' && c2 == '0' || c1 == '0' && c2 == '1' || c1 == '#' && c2 == '#') return true; 9 return false; 10 } 11 12 int main() { 13 int n; 14 scanf("%d", &n); 15 scanf("%s", str); 16 int len = 0; 17 s[len] = '$'; s[++len] = '#'; 18 for(int i = 0; i < n; i++) { s[++len] = str[i]; s[++len] = '#'; } 19 int mx = 0, id = 0; 20 long long ans = 0; 21 for(int i = 1; i <= len; i++) { 22 if(mx > i) p[i] = min(p[id*2-i], mx - i); 23 else p[i] = 1; 24 while(1 <= i - p[i] && i + p[i] <= len && check(s[i-p[i]], s[i+p[i]])) p[i]++; 25 if(s[i] == '#') { 26 ans += p[i] / 2; 27 if(mx < p[i] + i) { mx = p[i] + i; id = i; } // 只有s[i]为'#'才可以更新mx 28 } 29 } 30 for(int i = 1; i <= len; i++) printf("%d: %c %d ", i, s[i], p[i]); 31 printf("%lld ", ans); 32 return 0; 33 }