Warning: session_start(): open(/tmp/sess_07d2afc9de93b518bce91bdfa15f3779, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== $exKMP$ ====== ===== 算法思想 ===== $exKMP$ 可以求得模式串和文本串的后缀的最长公共前缀 $z$ 数组是自己的后缀和自己的最长公共前缀 $extend$ 数组是文本串的后缀和模式串的最长公共前缀这里 $s$ 是文本串， $t$ 是模式串 ===== 代码实现 =====

 

#include
using namespace std;

const int maxn=20000100;
char s[maxn],t[maxn];
int lens,lent,z[maxn],extend[maxn];
void solve_z(){
	z[1]=lent;
	for(int i=2,l=0,r=0;i<=lent;i++){
    	if(i<=r) z[i]=min(z[i-l+1],r-i+1);
    	while(i+z[i]<=lent&&t[i+z[i]]==t[z[i]+1]) ++z[i];
    	if(i+z[i]-1>r) l=i,r=i+z[i]-1;
  	}
  	long long ans1=0,ans2=0;
  	for(int i=1;i<=lent;i++) ans1^=1ll*i*(z[i]+1);
}
void exkmp(){
  	solve_z();
  	for(int i=1,l=0,r=0;i<=lens;i++){
    	if(i<=r) extend[i]=min(z[i-l+1],r-i+1);
    	while(i+extend[i]<=lens&&s[i+extend[i]]==t[extend[i]+1]) ++extend[i];
    	if(i+extend[i]-1>r) l=i,r=i+extend[i]-1;
  	}
}
int main(){
  	scanf("%s%s",s+1,t+1);
  	lens=strlen(s+1);lent=strlen(t+1);
  	exkmp();
  	long long ans1=0,ans2=0;
  	//for(int i=1;i<=lent;i++) printf("%d\n",z[i]);
	//for(int i=1;i<=lens;i++) printf("%d\n",extend[i]);  
  	for(int i=1;i<=lent;i++) ans1^=1ll*i*(z[i]+1);
  	for(int i=1;i<=lens;i++) ans2^=1ll*i*(extend[i]+1);
  	printf("%lld\n%lld",ans1,ans2);
  	return 0;
}



备用：

#include

#define N 1000010 

using namespace std;

int q,nxt[N],extend[N];
string s,t;

void getnxt()
{
    nxt[0]=t.size();//nxt[0]一定是T的长度
    int now=0;
    while(t[now]==t[1+now]&&now+1<(int)t.size())now++;//这就是从1开始暴力
    nxt[1]=now;
    int p0=1;
    for(int i=2;i<(int)t.size();i++)
    {
        if(i+nxt[i-p0]p的情况
            while(t[now]==t[i+now]&&i+now<(int)t.size())now++;//暴力
            nxt[i]=now;
            p0=i;//更新p0
        }
    }
}

void exkmp()
{
    getnxt();
    int now=0;
    while(s[now]==t[now]&&nowp的情况
            while(t[now]==s[i+now]&&now<(int)t.size()&&now+i<(int)s.size())now++;//暴力
            extend[i]=now;
            p0=i;//更新p0
        }
    }
}

int main()
{
    cin>>s>>t;
    exkmp();
    int len=t.size();
    for(int i=0;i