链接：https://ac.nowcoder.com/acm/contest/3/J
来源：牛客网

Just A String
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
何老师手中有一个字符串S，他发现这个字符串有一个神奇的性质，取出一个长为i的前缀（就是由S的前i个字符顺序构成的字符串）prei和一个长为j的后缀（就是由S的后j个字符顺序构成的字符串）sufj之后，总是存在三个字符串A,B,C（可能为空）使得prei=A+B,sufj=B+C， 虽然这听起来像是一句废话。
显然三元组A,B,C不总是唯一的，何老师从所有可能的三元组中找到B最长的，很容易知道这样的三元组是唯一的，并且认为prei和sufj的契合度就是f(i,j)=|A||B|2|C|，现在你需要帮何老师算出所有f(i,j)(0 ≤ i,j ≤ n)的异或和。
这里|X|表示字符串X的长度，X+Y表示将两个字符串X和Y顺序拼接起来后得到的新字符串。
输入描述:
第一行是一个正整数T(≤ 500)，表示测试数据的组数， 每组测试数据，包含一个仅由小写字母构成的非空字符串S(|S| ≤ 2000)， 保证满足|S|>200的数据不超过5组。
输出描述:
对于每组测试数据，输出所有f(i,j)(0 ≤ i,j ≤ n)的异或和。
示例1
输入
复制
1
abcab
输出
复制
13

题意：

思路：
纯暴力的算法显然是nnn 的时间复杂度，稳稳的TLE，
我们可以通过利用kmp算法来优化一个n，使其是n*n 的时间复杂度。

我们通过枚举给定字符串str的后缀temp字符串，然后构建next数组与整个字符串str进行匹配，我们知道这个kmp的匹配过程用两个下标变量进行滑动，

 if(str1[x]==str2[y])
        {
            // 只需要加这三行
            int len=y+1;
            ll a=x+1-len;ll b=len;ll c=m-len;
            // cout<<a<<" "<<b<<" "<<c<<" "<<ans<<" "<<a*b*b*c<<endl;
            ans^=(a*b*b*c);
            // db(ans);
            x++;
            y++;
        }

里面遇到两个字符相等的时候，我们是让其下标都+1，而我们可以在+1之前计算出以当前后缀字符串与x+1长度前缀字符串对答案的贡献值，这里主要通过next数组对 题意中要求的B数值进行的优化，因为想让一个情况对答案有贡献，前提是a,b,c 均不为0，不然一个数异或0没有影响，。那么B不为0的情况就可以在kmp匹配过程中所有str1[x]==str2[y] 情况中计算。代码中有细节注释

细节见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
string str;
int Next[5000];
void getnext(string str)
{
    int len=str.length();
    Next[0]=-1;
    int i=0;
    int j=-1;
    while(i<len)
    {
        if(j==-1||str[i]==str[j])
        {
            i++;j++;
            Next[i]=j;
        }else
        {
            j=Next[j];
        }
    }
}
ll ans=0ll;
int kmp(string str1,string str2,int k)// 从k下标开始查找
{
    int x,y;
    y=0;
    x=k;
    int n,m;
    n=str1.length();
    m=str2.length();
    getnext(str2);//  获得next数组
    while(x<n&&y<m)
    {
        if(str1[x]==str2[y])
        {
            // 只需要加这三行
            int len=y+1;
            ll a=x+1-len;ll b=len;ll c=m-len;
            // cout<<a<<" "<<b<<" "<<c<<" "<<ans<<" "<<a*b*b*c<<endl;
            ans^=(a*b*b*c);
            // db(ans);
            x++;
            y++;
        }else if(y==0)
        {
            x++;
        }else
        {
            y=Next[y];
        }
        if(y==m)
        {
            y=Next[y]; // 如果不考虑重叠的，这里置零
            // return x+1-str2.length();// 返回第一个匹配成功的起始位置
        }
    }
    return 0;
}
int main()
{
    // freopen("D:\\code\\text\\input.txt","r",stdin);
    //freopen("D:\\code\\text\\output.txt","w",stdout);
    int t;
    cin>>t;
    while(t--)
    {
        ans=0ll;
        cin>>str;
        int n=str.length();
        for(int i=0;i<n;i++)
        {
            string temp=str.substr(i);// 获得str从i开始到结束的后缀字符串
            kmp(str,temp,0);
        }
        cout<<ans<<endl;
    }
    
    
    
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}