1.KMP算法
next[i]表示模式串P[1, i]中相等前后缀的最长长度
双指针 i指针不回退，j指针来回跑.前面串的最长长度+if(p[i+1]=p[j]);找(最长相等前后缀)+用
时间复杂度O(m+n)
#include <bits/stdc++.h>
using namespace std;const int N = 1000010;
int m, n;
char S[N], P[N];
int ne[N];int main(){
cin >> S+1 >> P+1;
m = strlen(S+1), n = strlen(P+1);
// 计算next函数
ne[1] = 0;
for(int i = 2, j = 0; i <= n; i ++){
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) printf("%d\n", i-n+1);
}
for(int i = 1; i <= n; i ++)
printf("%d ", ne[i]);
return 0;
}
2.字符串哈希——把字符串映射成一个p进制的数字
求一个字符串的哈希值相当于求前缀和，O(n)
前缀和：h[i]=h[i-1]×p+s[i] , h[0]=0;
求一个字符串的字串的哈希值相当于求区间和O(1)
区间和：h[l,r]=h[r]-h[l-1]×(p^(r-l+1));
#include <iostream>
using namespace std;typedef unsigned long long ULL;
const int N = 1000010, P = 131;
int n, m;
char s[N];// p[i]=P^i, h[i]=s[1~i]的hash值
ULL p[N], h[N];// 预处理 hash函数的前缀和
void init(){
p[0] = 1, h[0] = 0;
for(int i = 1; i <= n; i ++){
p[i] = p[i-1]*P;
h[i] = h[i-1]*P+s[i];
}
}
// 计算s[l~r]的 hash值
ULL get(int l, int r){
return h[r]-h[l-1]*p[r-l+1];
}
// 判断两子串是否相同
bool substr(int l1,int r1,int l2,int r2){
return get(l1, r1) == get(l2, r2);
}int main(){
cin >> n >> m;
scanf("%s", s + 1);init();
while(m --){
int a, b, c, d;
cin >> a >> b >>c >> d;
if(substr(a,b,c,d)) puts("Yes");
else puts("No");
}
return 0;
}
3.字典树（Trie）
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int N=100010;
int n;
char s[N];
int ch[N][26],cnt[N],idx;void insert(char *s){
int p=0;
for(int i=0; s[i]; i ++){
int j=s[i]-'a';//字母映射
if(!ch[p][j])ch[p][j]=++idx;
p=ch[p][j];
}
cnt[p]++;//插入次数
}
int query(char *s){
int p=0;
for(int i=0; s[i]; i ++){
int j=s[i]-'a';
if(!ch[p][j]) return 0;
p=ch[p][j];
}
return cnt[p];
}
int main(){
scanf("%d",&n);
while(n--){
char op;
scanf("%s%s",&op,s);
if(op=='I')insert(s);
else printf("%d\n",query(s));
}
return 0;
}
4.AC自动机O(26n+m)
回跳边是指向父节点的回跳边所指节点的儿子(四边)
1.初始回跳边数组ne[v]为0;2儿子存在建回跳边3.指向父节点的回跳边所指节点的儿子,若儿子不存在则回跳0;4.这样类似递归的建边就可以找到当前节点的最长后缀(真)；
转移边所指节点一定是当前节点的最短路(三角)
1.初始回数组ch[u][i]存树边的终点和转移边的终点2.找到当前节点回跳边所指节点的儿子
通过BFS遍历判断节点儿子是否存在，存在建回跳边，不存在建转移边
搜索时跳边转移
// Luogu P3808 【模板】AC 自动机（简单版）
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;const int N=500010;
int n;char str[1000010];
int ch[N][26],cnt[N],idx;
int ne[N];void insert(char *s){//建树
int p=0;
for(int i=0;s[i];i++){
int j=s[i]-'a';
if(!ch[p][j])ch[p][j]=++idx;
p=ch[p][j];
}
cnt[p]++;
}
void build(){//建AC自动机
queue<int> q;
for(int i=0;i<26;i++)
if(ch[0][i])q.push(ch[0][i]);
while(q.size()){
int u=q.front();q.pop();
for(int i=0;i<26;i++){
int v=ch[u][i];
if(v)ne[v]=ch[ne[u]][i],q.push(v);
else ch[u][i]=ch[ne[u]][i];
}
}
}
int query(char *s){
int ans=0;
for(int k=0,i=0;s[k];k++){
i=ch[i][s[k]-'a'];
for(int j=i;j&&~cnt[j];j=ne[j])
ans+=cnt[j], cnt[j]=-1;
}
return ans;
}
int main(){
cin>>n;
for(int i=0;i<n; i++)
cin>>str, insert(str);
build();
cin>>str;
cout<<query(str)<<endl;
return 0;
}
5.后缀数组（O(nlogn)）
后缀数组sa[i]表示排序为i的后缀编号。
名次数组rank[i]表示后缀i的排名
高度数组height[i]=LCP(sa[i],sa[i-1]) 第i名后缀与第i-1名后缀的最前公共前缀的长度。
倍增法:串的宽度成倍增加，通过偏移量获取桶号。
桶排序:同则入同桶，不同则加桶。正序累计，逆序拿取。
多重映射：函数层层嵌套，一层一层往外拿
// Luogu P3809 【模板】后缀排序
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;const int N=2000010;
char s[N];
int n,m;//n为后缀个数, m为桶的个数
int x[N],y[N],c[N],sa[N],rk[N],height[N];
//桶数组x[i],辅助数组y[i],计数数组c[i]
void get_sa(){
int i,j,k;
//按第一个字母排序
for(i=1;i<=n;i++)c[x[i]=s[i]]++;
for(i=1;i<=m;i++)c[i]+=c[i-1];
for(i=n;i;i--)sa[c[x[i]]--]=i;
for(k=1;k<=n;k<<=1){ //logn轮
//按第二关键字排序
memset(c,0,sizeof(c));
for(i=1;i<=n;i++)y[i]=sa[i];
for(i=1;i<=n;i++)c[x[y[i]+k]]++;
for(i=1;i<=m;i++)c[i]+=c[i-1];
for(i=n;i;i--)sa[c[x[y[i]+k]]--]=y[i];
//按第一关键字排序
memset(c,0,sizeof(c));
for(i=1;i<=n;i++)y[i]=sa[i];
for(i=1;i<=n;i++)c[x[y[i]]]++;
for(i=1;i<=m;i++)c[i]+=c[i-1];
for(i=n;i;i--)sa[c[x[y[i]]]--]=y[i];
//把后缀放入桶数组
for(i=1;i<=n;i++)y[i]=x[i];
for(m=0,i=1;i<=n;i++)
if(y[sa[i]]==y[sa[i-1]]&&
y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=m;
else x[sa[i]]=++m;
if(m==n)break;//已排好
}
}
void get_height(){
int i,j,k;
for(i=1;i<=n;i++)rk[sa[i]]=i;
for(i=1,k=0;i<=n;i++){ //枚举后缀i
if(rk[i]==1)continue;//第一名height为0
if(k)k--;//上一个后缀的height值减1
int j=sa[rk[i]-1];//找出后缀i的前邻后缀j
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
height[rk[i]]=k;
}
}
int main(){
scanf("%s",s+1);
n=strlen(s+1); m=122;
get_sa();
get_height();
for(int i=1;i<=n;i++)printf("%d ",sa[i]);
// puts("");
// for(int i=1;i<=n;i++)printf("%d ",height[i]);
return 0;
}