2021.11.11 EXKMP
https://www.luogu.com.cn/problem/P5410
下标以1开头：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e7+10;
typedef long long ll;
int lenp,lens,z[N],ext[N];
char t[N],s[N];
inline void getz(char *s){
int n=strlen(s+1);
memset(z,0,sizeof(z));
z[1]=n;
for(int i=2,l=0,r=0;i<=n;i++){
if(i<=r)z[i]=min(z[i-l+1],r-i+1);
while(i+z[i]<=n&&1+z[i]<=n&&s[z[i]+1]==s[(i+z[i]-1)+1])++z[i];
if(i+z[i]-1>r)l=i,r=i+z[i]-1;
}
//z[0]=n;
//cout<<"z "<<endl;//
//for(int i=0;i<=n;i++)cout<<z[i]<<" ";cout<<endl;//
}
inline void exkmp(char *s,char *t){
int n=strlen(s+1),m=strlen(t+1);
getz(t);
ll ans=0;
for(int i=1;i<=m;i++)ans^=1ll*(i)*(z[i]+1);
cout<<ans<<endl;
memset(ext,0,sizeof(ext));
for(int i=1,l=0,r=0;i<=n;i++){
if(i<=r)ext[i]=min(z[i-l+1],r-i+1);
while(i+ext[i]<=n&&1+ext[i]<=m&&t[ext[i]+1]==s[(i+ext[i]-1)+1])++ext[i];
if(r<i+ext[i]-1)l=i,r=i+ext[i]-1;
}
ans=0;
for(int i=1;i<=n;i++)ans^=1ll*(i)*(ext[i]+1);
cout<<ans;
//cout<<"ext"<<endl;//
//for(int i=0;i<=n;i++)cout<<ext[i]<<" ";cout<<endl;//
}
int main(){
scanf("%s",s+1);scanf("%s",t+1);
exkmp(s,t);
return 0;
}
下标以0开始：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e7+10;
typedef long long ll;
int lenp,lens,z[N],ext[N];
char t[N],s[N];
inline void getz(char *s){
int len=strlen(s);
memset(z,0,sizeof(z));
z[0]=len;
for(int i=1,l=0,r=0;i<len;i++){
if(i<=r)z[i]=min(z[(i-l+1)-1],r-i+1);
while(i+z[i]<len&&s[z[i]]==s[(i+z[i]-1)+1])++z[i];
if(i+z[i]-1>r)l=i,r=i+z[i]-1;
}
ll ans=0;
for(int i=0;i<len;i++)ans^=1ll*(i+1)*(z[i]+1);
cout<<ans<<endl;
}
inline void exkmp(char *s,char *t){
getz(t);
int lens=strlen(s),lent=strlen(t);
for(int i=0,l=-1,r=-1;i<lens;i++){
if(i<=r)ext[i]=min(z[(i-l+1)-1],r-i+1);
while(i+ext[i]<lens&&ext[i]<lent&&t[ext[i]]==s[(i+ext[i]-1)+1])++ext[i];
if(i+ext[i]-1>r)l=i,r=i+ext[i]-1;
}
ll ans=0;
for(int i=0;i<lens;i++)ans^=1ll*(i+1)*(ext[i]+1);
cout<<ans<<endl;
}
int main(){
scanf("%s",s);scanf("%s",t);
exkmp(s,t);
return 0;
}
练习题
https://www.luogu.com.cn/problem/CF432D
论树状数组的好用 ~
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
int z[N],ext[N],t[N],top;
char s[N*2];
struct node{
int len,tot;
bool operator <(const node &b)const{
return len<b.len;
}
}ans[N];
inline void getz(char *s){
int n=strlen(s+1);
z[1]=n;
for(int i=2,l=0,r=0;i<=n;i++){
if(i<=r)z[i]=min(z[i-l+1],r-i+1);
while(i+z[i]<=n&&s[z[i]+1]==s[(i+z[i]-1)+1])++z[i];
if(i+z[i]-1>r)l=i,r=i+z[i]-1;
}
}
inline void exkmp(char *s,char *t){
int lens=strlen(s+1),lent=strlen(t+1);
getz(t);
for(int i=1,l=-1,r=-1;i<=lens;i++){
if(i<=r)ext[i]=min(z[i-l+1],r-i+1);
while(i+ext[i]<=lens&&1+ext[i]<=lent&&t[ext[i]+1]==s[(i+ext[i]-1)+1])++ext[i];
if(i+ext[i]-1>r)l=i,r=i+ext[i]-1;
}
}
inline int lowbit(int x){
return x&-x;
}
inline void add(int x,int k,int len){
for(int i=x;i<=len;i+=lowbit(i))t[i]+=k;
}
inline int query(int x){
int fin=0;
for(int i=x;i>0;i-=lowbit(i))fin+=t[i];
return fin;
}
int main(){
scanf("%s",s+1);
int len=strlen(s+1);
//cout<<len<<endl;
s[len+1]='|';
for(int i=1;i<=len;i++)s[i+len+1]=s[i];
//for(int i=1;i<=len*2+2;i++)printf("%c",s[i]);cout<<endl;
int leni=strlen(s+1);
//cout<<leni<<endl;
getz(s);
//for(int i=1;i<=leni;i++)cout<<z[i]<<" ";cout<<endl;
for(int i=len+2;i<=leni;i++)if(z[i])add(z[i],1,len);
for(int i=len+2;i<=leni;i++)if(i+z[i]-1==leni){
++top;
ans[top].len=z[i];ans[top].tot=query(len)-query(z[i]-1);
}
sort(ans+1,ans+top+1);
cout<<top<<endl;
for(int i=1;i<=top;i++)cout<<ans[i].len<<" "<<ans[i].tot<<endl;
return 0;
}
https://www.luogu.com.cn/problem/P7114
https://www.luogu.com.cn/blog/nitubenben/solution-p7114
PS：树状数组是EXKMP的好帮手~
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=(1<<20)+10;
typedef long long ll;
int t,z[N],before[N],after[N],tree[N];
char s[N];
inline void getz(char *s){
int n=strlen(s);
z[0]=n;
for(int i=1,l=0,r=0;i<n;i++){
if(i<=r)z[i]=min(z[(i-l+1)-1],r-i+1);
while(i+z[i]<n&&s[z[i]]==s[(i+z[i]-1)+1])++z[i];
if(i+z[i]-1>r)l=i,r=i+z[i]-1;
}
}
inline int lowbit(int x){
return x&-x;
}
inline void add(int x,int k,int n){
for(int i=x;i<=n;i+=lowbit(i))tree[i]+=k;
}
inline int query(int x){
int fin=0;
for(int i=x;i>0;i-=lowbit(i))fin+=tree[i];
return fin;
}
int main(){
cin>>t;
while(t--){
memset(z,0,sizeof(z));
memset(after,0,sizeof(after));
memset(before,0,sizeof(before));
memset(tree,0,sizeof(tree));
scanf("%s",s);
getz(s);
int n=strlen(s);
for(int i=0;i<n;i++)if((i+z[i]-1)+1==n)--z[i];
for(int i=0;i<n;i++)++after[s[i]-'a'];
int all=0,pre=0,suf=0;
ll ans=0;
for(int i=0;i<26;i++)if(after[i]&1)++all;
suf=all;
for(int i=0;i<n;i++){
int x=s[i]-'a';
if(after[x]&1)--suf;
else ++suf;
--after[x];
if(before[x]&1)--pre;
else ++pre;
++before[x];
if(i&&i!=n-1){
int num=z[i+1]/(i+1)+1;
ans+=1ll*(num/2)*query(all+1)+1ll*(num-num/2)*query(suf+1);
}
add(pre+1,1,n);
}
cout<<ans<<endl;
}
return 0;
}
