P5410 【模板】扩展 KMP/exKMP(Z 函数)

2023-12-23 19:36:53

【模板】扩展 KMP/exKMP(Z 函数)

题目描述

给定两个字符串 a , b a,b a,b,你要求出两个数组:

  • b b b z z z 函数数组 z z z,即 b b b b b b 的每一个后缀的 LCP 长度。
  • b b b a a a 的每一个后缀的 LCP 长度数组 p p p

对于一个长度为 n n n 的数组 a a a,设其权值为 xor ? i = 1 n i × ( a i + 1 ) \operatorname{xor}_{i=1}^n i \times (a_i + 1) xori=1n?i×(ai?+1)

输入格式

两行两个字符串 a , b a,b a,b

输出格式

第一行一个整数,表示 z z z 的权值。

第二行一个整数,表示 p p p 的权值。

样例 #1

样例输入 #1

aaaabaa
aaaaa

样例输出 #1

6
21

提示

样例解释:

z = { 5 ? 4 ? 3 ? 2 ? 1 } z = \{5\ 4\ 3\ 2\ 1\} z={5?4?3?2?1} p = { 4 ? 3 ? 2 ? 1 ? 0 ? 2 ? 1 } p = \{4\ 3\ 2\ 1\ 0\ 2\ 1\} p={4?3?2?1?0?2?1}


数据范围:

对于第一个测试点, ∣ a ∣ , ∣ b ∣ ≤ 2 × 1 0 3 |a|,|b| \le 2 \times 10^3 a,b2×103

对于第二个测试点, ∣ a ∣ , ∣ b ∣ ≤ 2 × 1 0 5 |a|,|b| \le 2 \times 10^5 a,b2×105

对于 100 % 100\% 100% 的数据, 1 ≤ ∣ a ∣ , ∣ b ∣ ≤ 2 × 1 0 7 1 \le |a|,|b| \le 2 \times 10^7 1a,b2×107,所有字符均为小写字母。

思路:

扩展 KMP版题,不会的可以看看这篇题解,讲的很好哦ヾ(≧▽≦*)o
超级好题解

代码

#include<bits/stdc++.h>
using namespace std;
long long ans,cnt,nxt[20000010],ext[20000010];
string a,b;
void getZ(string s){
	int k=1,
	len=s.size();
	nxt[0]=len;
	int p=0;
	while(p+1<len&&s[p]==s[p+1]) p++;
	nxt[1]=p;
	for(int i=2;i<len;i++){
		int p=nxt[k]+k-1;
		int l=nxt[i-k];
		if(i+l<=p) nxt[i]=l;
		else{
			int j=max(0,p-i+1);
			while(i+j<len&&s[i+j]==s[j]) j++;
			nxt[i]=j;
			k=i;
		}
	}
}

void exkmp(string a,string b){
	int k=0;
	int la=a.size();
	int lb=b.size();
	int p=0;
	while(p<la&&p<lb&&a[p]==b[p]) p++;
	ext[0]=p;
	for(int i=1;i<la;i++){
		int p=ext[k]+k-1;
		int l=nxt[i-k];
		if(i+l<=p) ext[i]=l;
		else{
			int j=max(0,p-i+1);
			while(i+j<la&&j<lb&&a[i+j]==b[j]) j++;
			ext[i]=j;
			k=i;
		}
	}
}
int main(){
	cin>>a>>b;
	getZ(b);
	
	exkmp(a,b);
	for(int i=0;i<b.size();i++){
		ans^=(i+1)*(nxt[i]+1);
	}
	for(int i=0;i<a.size();i++){
		cnt^=(i+1)*(ext[i]+1);
	}
	cout<<ans<<endl;
	cout<<cnt;
	return 0;
} 

文章来源:https://blog.csdn.net/m0_61360607/article/details/135164855
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。