kmp

题意：

分析：

这一题，我最初很没思路。刚开始想会不会是kmp扩展，但是琢磨一番发现无法解决。
然后，在进行手工推算时，发现这是个kmp问题。

请看：
题目让我们求的是：
对于字符串s,判断他的每一个前缀和每一个后缀的B
是否？

从题目所给的数据量来看，我们很简单就能想到枚举。
但是，即便枚举我们也只能承受n^2级别的。
即，我们可以枚举每一个后缀去和每一个前缀进行比较，判断。
这个比较判断的时间，至关重要。我们应该使其尽量的短。

接下来我们看看，如何进行判断的：

s1表前缀，s2表后缀。
我们看：如果此时s1的2，3，4与s2的1，2，3匹配。他们为最大匹配。
那么，当我们的前缀再往后进一格呢？

这时，需要分类讨论了：
1.如果s1的5与s2的4匹配，那么此时的最大匹配就是4即B就为4
这是一定的，因为倘若有一个更大的匹配，比如1,2,3,4,5那么在上一次匹配中2,3,4就不是最大匹配了！
2,如果s1的5和s2的4不匹配呢？
我们想想，在最终匹配的B中s1的5是一定要匹配上的。因为他在终点！
又，基于上面1的证明，是不可能再比上一次的匹配大了。
所以我们要对s2的4往前找。
假设我们找到了3那么判断3是否为s1的5时，我们一定要保证s2的1，2等于s1的3，4
而s1的3，4等于s2的2，3.
有没有感到一丝丝熟悉？这不就是我们求解kmp的next[]的操作嘛！！
即，一旦发现比较处不是s1的5我们就让j=net[j]跳到下一个比较的位置。
一旦有一个==那么此地就是最大匹配
当j==-1时，意味没有一个为5B为空的

3.也是基于2的一个特殊情况
如果我们s2都匹配完了，但是s1还在增加该怎么办?
即：

假设s1(1,2,3,4,5)==s2(1,2,3,4,5)
然后此时要匹配s1[6]
我们该怎么办？
直接让j=net[j]就好了。(并不难理解，认清问题，画画图)

代码如下：

#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int max_n = 2100;
inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    while (!isdigit(c)) { if (c == '-')f = -1;c = getchar(); }
    while (isdigit(c))x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x * f;
}

inline string readstring()
{
    char ch = getchar();
    string st1 = "";
    while (!((ch >= 'a') && (ch <= 'z')))
        ch = getchar();
    while (((ch >= 'a') && (ch <= 'z')))
        st1 += ch, ch = getchar();
    return st1;
}
inline void write(ll x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}
inline void copy(string& s, string& p) {
    p.clear();
    for (register int i = 0;i < s.size();++i)p += s[i];
}
int net[max_n];
inline void getnext(string& p) {
    register int i = 0;register int j = -1;
    net[0] = -1;
    while (i < p.size()) {
        if (j == -1 || p[i] == p[j])net[++i] = ++j;
        else j = net[j];
    }
}
int main() {
    int T = read();
    register string s;
    register string p;
    while (T--) {
        register ll ans = 1;
        s = readstring();
        copy(s, p);
        for (int i = 0;i < p.size();++i) {
            string behind = p.substr(i);
            register int pos = 0;getnext(behind);
            for (register int j = 0;j < s.size();++j) {
                while (true) {
                    if (pos == behind.size())
                        pos = net[pos];
                    if (pos == -1 || s[j] == behind[pos]) {
                        ++pos;
                        break;
                    }
                    else pos = net[pos];
                }
                int B = pos;
                int A = j + 1 - B;
                int C = behind.size() - B;
                ll res = (ll)A * B * B * C;
                ans = ans ^ res;
            }
        }write(ans ^ 1);putchar('\n');
    }
}