C++ 代码
/*
1.
跑一遍生成next的过程,例如:
0 1 2 3 4 5 6 7
* a b c a b c z
//这里巧妙的运用了前面的字符是否相等,来判断是否当出现相同字符时候返回的位置
i = 2, j = 0 | p(2) != p(1) | ne(2) = 0 // j 尝试出门,不匹配,失败,回家。
i = 3, j = 0 | p(3) != p(1) | ne(3) = 0 // j 再尝试出门,还是不行,回老家。
i = 4, j = 0 | p(4) == p(1) | ne(4) = 1 // j 再尝试出门,发现了相同的!出门!并且做记录。
i = 5, j = 1 | p(5) == p(2) | ne(5) = 2 // j 继续走,发现还是可以,记录
i = 6, j = 2 | p(6) == p(3) | ne(6) = 3 //状态不错,继续走
i = 7, j = 3 | p(7) != p(4) | j = ne(3) = 0 | ne(7) =0 //碰壁了,尝试从3开始重新尝试,但是3最后退回老家,sad。
j代表距离,如果和当前i位置匹配,j继续走,如果不比配,j尽可能往回退,退无可退,就回到了快乐老家 (0)。
*/
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=1e6+10;
int n,m;
char p[N],s[M];//p是子串,s是主串
int ne[N];//这里存储子串匹配指针的回溯位置
int main()
{
cin>>n>>p+1>>m>>s+1;//从1位置开始匹配可以防止边界出错
//求next,注意我们的主串一直在向前走.只是因为子串里面有相同的串,所以我们可以在字串里面回溯;以便得到一个和主串之前走过的相同的长度匹配位置,这样就可以减少匹配的几次;因为没有了无效的匹配
for(int i=2,j=0;i<=n;++i)//注意我们计算nxt的时候是自己和自己比较,开始的时候我们需要比较第二个位置和第一个位置
{
while(j&&p[i]!=p[j+1])j=ne[j];
if(p[i]==p[j+1])++j;
ne[i]=j;
}
//kmp配对
for(int i=1,j=0;i<=m;++i)
{
while(j&&s[i]!=p[j+1])j=ne[j];//我们比较的是主串与子串回溯指针的后一个位置
//当子串处于第一个位置不需要回溯
if(s[i]==p[j+1])++j;//比较主串和子串
if(j==n)//这样表示匹配成功
{
cout<<i-n<<" ";//i是主串和字串匹配的最后一个位置,所以需要减去字串的长度;这里从1开始存储,但是要求从0开始输出,所以我们不需要i-n+1的+1操作
j=ne[j];//匹配成功到头了,必须回退才能继续比较
}
}
return 0;
}
//核心思想:在每次失配时,不是把p串往后移一位,而是把p串往后移动至下一次可以和前面部分匹配的位置,这样就可以跳过大多数的失配步骤。而每次p串移动的步数就是通过查找next[ ]数组确定的。
2.前缀方法
#include<bits/stdc++.h>
//#define x first
//#define y second
//#define MAXN 200011
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N=1e6+10;
vector<int>prefix_function(string s)
{
int n=s.size();
vector<int>pi(n);
for(int i=1;i<n;++i)
{
int j=pi[i-1];
while(j>0&&s[i]!=s[j])j=pi[j-1];
if(s[i]==s[j])++j;
pi[i]=j;
}
return pi;
}
vector<int>find_occurrences(string text,string pattern)
{
string cur=pattern+"#"+text;
int sz1=text.size(),sz2=pattern.size();
vector<int>v;
vector<int>lps=prefix_function(cur);
for(int i=sz2+1;i<=sz1+sz2;++i)
{
if(lps[i]==sz2)v.push_back(i-2*sz2);
}
return v;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int nn;
string s1,s2;
cin>>nn>>s2>>nn>>s1;//先输入模式串再输入被匹配串
vector<int>vec=find_occurrences(s1,s2);//文本串和模式串
for (auto i:vec)cout<<i<<" ";
return 0;
}