题目链接: https://www.luogu.org/problem/P5410
题意: 给两个字符串 a,b, 求 b 对 a 的每一个后缀的最大前缀长度
分析: 扩展 KMP(又称 Z-algorithm 算法) 裸题
该博客讲解的比较好:
但他有几个地方讲的有几个问题, 主要在情况 2 里面
首先是一开始 S[K+L] 肯定是在 p 的后面, 这个比较明显
然后情况二红蓝绿三条线的序列不是一样的, 红绿还是一样的, 但是蓝线就不等了, 这个自己看一看
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn=1e5+7;// 单词间自行添加了符号, 稍做扩大
- const ll inf=1e18;
- #define meminf(a) memset(a,0x3f,sizeof(a))
- #define mem0(a) memset(a,0,sizeof(a));
- char a[maxn],b[maxn];
- int nxt[maxn],extend[maxn];//nxt[i] 代表 b[i...len] 和 b 的最大前缀长度, extend[i] 代表 a[i...len] 和 b 的最大前缀长度
- void getnxt(){
- int len=strlen(b);
- nxt[0]=len;//nxt[0] 就是原串情况下, 自然就为 len
- int now=0;
- while(b[now]==b[now+1]&&now+1<len) now++;
- nxt[1]=now;
- int p0=1;//p0 是满足 p0+nxt[p0]-1 最大的点, 一开始初始化为 1
- for(int i=2;i<len;i++){
- if(i+nxt[i-p0]<p0+nxt[p0]) nxt[i]=nxt[i-p0];
- //i 相当于 k+1,nxt[i-p0] 相当于 L(nxt[k-p0+2) 这里字符串是从 0 开始的, 和博客里面从 1 开始的区别是少加一个 1
- else{
- int now=p0+nxt[p0]-i;
- now=max(now,0);// 防止 i 在 p 的后面
- while(b[now]==b[i+now]&&i+now<len) now++;
- nxt[i]=now;
- p0=i;// 更新 p0
- }
- }
- }
- void exkmp(){
- getnxt();
- int len=strlen(a);
- int now=0;
- while(a[now]==b[now]&&now<min(strlen(a),strlen(b))) now++;
- extend[0]=now;
- int p0=0;
- for(int i=1;i<len;i++){
- if(i+nxt[i-p0]<extend[p0]+p0) extend[i]=nxt[i-p0];
- else{
- int now=p0+extend[p0]-i;
- now=max(now,0);
- while(b[now]==a[i+now]&&now<strlen(b)&&i+now<len) now++;
- extend[i]=now;
- p0=i;
- }
- }
- }
- int main(){
- scanf("%s%s",a,b);
- exkmp();
- for(int i=0;i<strlen(b);i++) printf("%d",nxt[i]);
- putchar('\n');
- for(int i=0;i<strlen(a);i++) printf("%d",extend[i]);
- putchar('\n');
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3165085.html