首页 > 代码库 > kmp字符串匹配基础模板题 (洛谷P3375 )
kmp字符串匹配基础模板题 (洛谷P3375 )
如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。
为了减少骗分的情况，接下来还要输出子串的前缀数组next。如果你不知道这是什么意思也不要问，去百度搜[kmp算法]学习一下就知道了。
输入样例#1：
ABABABC ABA
输出样例#1：
1 3 0 0 1
因为要求next的值，所以这里不加优化了
把代码进行稍微的改动标记即可
#include<bits/stdc++.h>
using namespace std;
int next[2000000];
char s[2000000],p[2000000];
int answer[200000];
int top=0;
void Getnext()
{
int len=strlen(p);
next[0]=-1;
int k=-1,j=0;
while(j<len)//注意下标
{
//p[k]表示前缀，p[j]表示后缀
if(k==-1||p[j]==p[k])
{
k++;j++;
// if(p[j]!=p[k])
next[j]=k;
//else//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]
// next[j]=next[k];
}
else k=next[k];
}
}
int kmp()
{
int i=0,j=0;
int lens=strlen(s),lenp=strlen(p);
while(i<lens&&j<lenp)
{
if(j==-1||s[i]==p[j])
{
i++;
j++;
}
else j=next[j];//相当于模式串向右移动
if(j==lenp)
{
cout<<i+1-j<<endl;
j=next[j];//将后缀转化为前缀
}
}
}
int main()
{
scanf("%s%s",s,p);
Getnext();
kmp();
for(int i=1;i<=strlen(p);i++)
cout<<next[i]<<" ";
return 0;
}
kmp字符串匹配基础模板题 (洛谷P3375 )
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。