算法简介：
- 真前后缀的意义：前后缀不相等。
- 注意方向都是正向的，而不是回文的字符串。
- 模版：
char s[N],p[M];
int nex[M];
int n=strlen(s+1),m=strlen(p+1);//字符串的下标从1开始
nex[0]=nex[1]=0;
for(int i=2,j=0;i<m;i++)
{
//不断匹配p[i]和p[j+1]
while(j&&p[i]!=p[j+1])j=nex[j];
if(p[i]==p[j+1])j++;//从while出来后要么j=0，要么匹配成功
nex[i]=j;
}
- 用nex数组去匹配s
for(int i=1,j=0;i<=n;i++)
{
while(j&&s[i]!=p[j+1])j=nex[j];//失配时移动
if(s[i]==p[j+1])j++;//成功匹配一个字符
if(j==m)//成功匹配一次
}
斤斤计较的小z–2047
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
char s[N],p[N];
int nex[N];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>p+1;int m=strlen(p+1);//模式串
cin>>s+1;int n=strlen(s+1);//文本串
//get next
nex[0]=nex[1]=0;
for(int i=2,j=0;i<=m;i++)
{
while(j&&p[i]!=p[j+1])j=nex[j];
if(p[i]==p[j+1])j++;
nex[i]=j;
}
//对s串进行匹配
int ans=0;
for(int i=1,j=0;i<=n;i++)
{
while(j&&s[i]!=p[j+1])j=nex[j];
if(s[i]==p[j+1])j++;
if(j==m)ans++;
}
cout<<ans<<endl;
return 0;
}
定义了一个字符数组s和p，分别用于存储文本串和模式串。同时定义了一个整数数组nex，用于存储模式串的next数组。
通过cin读取输入的模式串和文本串，并计算它们的长度。
初始化nex数组的前两个元素为0。
使用循环计算模式串的next数组。next数组用于记录模式串中每个位置之前的子串的最长公共前后缀长度。具体计算过程如下：
初始化指针j为0。
从模式串的第三个字符开始遍历，对于每个位置i：
如果当前字符与j+1位置的字符不相等，将j更新为nex[j]，即向前回溯到上一个匹配的位置。
如果当前字符与j+1位置的字符相等，将j加1。
将nex[i]更新为j，表示当前位置之前的子串的最长公共前后缀长度。
初始化变量ans为0，用于记录模式串在文本串中的出现次数。
使用循环对文本串进行匹配：
初始化指针j为0。
从文本串的第一个字符开始遍历，对于每个位置i：
如果当前字符与j+1位置的字符不相等，将j更新为nex[j]，即向前回溯到上一个匹配的位置。
如果当前字符与j+1位置的字符相等，将j加1。
如果j等于模式串的长度，说明找到了一个匹配，将ans加1。
输出结果ans，即模式串在文本串中的出现次数。
字符串hash
- 进制数一般是一个质数。
- hash的初始化
- 获取子串：
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
char s[N],p[N];
typedef unsigned long long ull;
const ull base =131;
int l,r;
ull h1[N],h2[N],b[N];//b数组用来存储base的多少次方
ull getHash(ull h[],int l,int r)
{
return h[r]-h[l-1]*b[r-l+1];
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>p+1;int m=strlen(p+1);//模式串
cin>>s+1;int n=strlen(s+1);//文本串
b[0]=1;//预处理b数组
for(int i=1;i<=n;i++)
{
b[i]=b[i-1]*base;
h1[i]=h1[i-1]*base+(int)p[i];
h2[i]=h2[i-1]*base+(int)s[i];
}
//开始枚举
int ans=0;
for(int i=1;i+m-1<=n;i++)
{
if(getHash(h1,l,m)==getHash(h2,i,i+m-1))ans++;
}
cout<<ans<<endl;
return 0;
}