北京师范大学第十五届ACM决赛-重现赛J Just A String （kmp算法延伸）
链接：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';
}
}
}
