【模板】KMP 字符串匹配
题目描述
给出两个字符串
s
1
s_1
s1 和
s
2
s_2
s2,若
s
1
s_1
s1 的区间
[
l
,
r
]
[l, r]
[l,r] 子串与
s
2
s_2
s2 完全相同,则称
s
2
s_2
s2 在
s
1
s_1
s1 中出现了,其出现位置为
l
l
l。
现在请你求出
s
2
s_2
s2 在
s
1
s_1
s1 中所有出现的位置。
定义一个字符串
s
s
s 的 border 为
s
s
s 的一个非
s
s
s 本身的子串
t
t
t,满足
t
t
t 既是
s
s
s 的前缀,又是
s
s
s 的后缀。
对于
s
2
s_2
s2,你还需要求出对于其每个前缀
s
′
s'
s′ 的最长 border
t
′
t'
t′ 的长度。
输入格式
第一行为一个字符串,即为
s
1
s_1
s1。
第二行为一个字符串,即为
s
2
s_2
s2。
输出格式
首先输出若干行,每行一个整数,按从小到大的顺序输出
s
2
s_2
s2 在
s
1
s_1
s1 中出现的位置。
最后一行输出
∣
s
2
∣
|s_2|
∣s2∣ 个整数,第
i
i
i 个整数表示
s
2
s_2
s2 的长度为
i
i
i 的前缀的最长 border 长度。
样例 #1
样例输入 #1
ABABABC
ABA
样例输出 #1
1
3
0 0 1
提示
样例 1 解释
。
对于
s
2
s_2
s2 长度为
3
3
3 的前缀 ABA
,字符串 A
既是其后缀也是其前缀,且是最长的,因此最长 border 长度为
1
1
1。
数据规模与约定
本题采用多测试点捆绑测试,共有 3 个子任务。
- Subtask 1(30 points): ∣ s 1 ∣ ≤ 15 |s_1| \leq 15 ∣s1∣≤15, ∣ s 2 ∣ ≤ 5 |s_2| \leq 5 ∣s2∣≤5。
- Subtask 2(40 points): ∣ s 1 ∣ ≤ 1 0 4 |s_1| \leq 10^4 ∣s1∣≤104, ∣ s 2 ∣ ≤ 1 0 2 |s_2| \leq 10^2 ∣s2∣≤102。
- Subtask 3(30 points):无特殊约定。
对于全部的测试点,保证 1 ≤ ∣ s 1 ∣ , ∣ s 2 ∣ ≤ 1 0 6 1 \leq |s_1|,|s_2| \leq 10^6 1≤∣s1∣,∣s2∣≤106, s 1 , s 2 s_1, s_2 s1,s2 中均只含大写英文字母。文章来源:https://www.toymoban.com/news/detail-626569.html
多了个next数组的输出文章来源地址https://www.toymoban.com/news/detail-626569.html
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define endl '\n'
#define lowbit(x) ((x)&-(x))
const int mod=1e9+7;
typedef long long ll;
ll ans=0,sum=0,x,y,n1,m1,l,r;
ll t,s1,s2,s3,s4,max1=0,min1=1e18,n,m,i,j,k;
ll u,v,w;
inline int read() {
bool sym=0;
int res=0;
char ch=getchar();
while(!isdigit(ch))sym |=(ch =='-'),ch=getchar();
while(isdigit(ch)) res =(res<<3)+(res<<1)+(ch^48),ch=getchar();
return sym ? -res : res;
}
void print(int x) {
if(!x)return;
print(x/10);
putchar(x%10+'0');
}
ll ne[1086];
char str[1086],pa[1086];
void getnext(char *p,ll plen){// 计算next[1]-->next[plen]
ne[0]=0;ne[1]=0;
for(ll i=1;i<plen;i++){//i的增加看作后缀的扩展
ll j=ne[i];//j的后移;j指向前缀阴影的后一个字符
while(j&&p[i]!=p[j])//阴影的后一个字符不相同
j=ne[j]; //更新 j
if(p[i]==p[j])
ne[i+1]=j+1; //递推
else
ne[i+1]=0; //赋 0
}
}
void kmp(char *s,char *p){ //s中找 p
ll last=-1;
ll slen=strlen(s);
ll plen=strlen(p);
getnext(p,plen);// 预计算next数组
ll j=0;
for( ll i=0;i<slen;i++){ //匹配 s,p的每个字符
while(j&&s[i]!=p[j]) // 失配了
j=ne[j]; // j滑动到next[j]位置
if(s[i]==p[j]) // 当前位置的字符匹配,继续
j++;
if(j==plen){ //j 到了p的末尾,找到了一个匹配
//cout<<i+1-plen<<" "<<s[i+1-plen]<<endl; //这个匹配的起点为 i+1-plen,末尾是i, 可输出
cout<<i+2-plen<<endl;
/*if(i-last>=plen){ //判断新的匹配和上一个匹配是否能分开
ans++;
last=i; // last 指向上一次匹配的末尾位置
} */
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>str;
cin>>pa;
kmp(str,pa);
for(i=1;i<=strlen(pa);i++)
cout<<ne[i]<<" ";
//cout<<ans;
return 0;
}
//mio lover
到了这里,关于P3375 【模板】KMP 字符串匹配的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!