KMP算法
前言
update 2024.7.31 今天重写了一篇 KMP 板子，之前是蒟蒻（现在也是），写的都是什么鬼，甚至没过模板题。感觉 KMP 优化没什么用，但是暂时保留吧。
简介
用模式串匹配文本串（主串）。
对于一个模式串，找出每个位置的 border（最长相等的前缀后缀），即为 \(next\) 数组。失陪时就跳到 border 的位置继续匹配（毕竟前缀是一样的）。注意加减细节。
KMP模板
#include <bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
using namespace std;
typedef long long ll;
const int N = 1e6+7;
char s1[N],s2[N];
int nex[N];
int l1,l2;
void getnex() {
int j=0;
rep(i,1,l2-1) {
while(j && s2[i]!=s2[j]) j=nex[j];
if(s2[i]==s2[j]) j++;
nex[i+1]=j;
}
}
void KMP() {
int j=0;
rep(i,0,l1-1) {
while(j && (s1[i]!=s2[j])) j=nex[j];
if(s1[i]==s2[j]) j++;
if(j==l2) {
pf("%d\n",i-j+2);
}
}
}
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#endif
sf("%s%s",s1,s2);
l1=strlen(s1),l2=strlen(s2);
getnex();
KMP();
rep(i,1,l2) pf("%d ",nex[i]);
}
KMP优化模板
#include<iostream>
#include<string>
#include<cstring>
#define ll long long
using namespace std;
const int N=105;
int ans;
struct node{
string s;
int len,next[N];
int next_val[N];
}s1,s2;
void get_next(node &ss){
int qz[N];
memset(qz,0,sizeof(qz));
ss.next[0]=-1;
ss.next_val[0]=-1;
for(int i=1;i<ss.len;i++){
int j=qz[i-1];
while(j>0&&ss.s[i]!=ss.s[j]) j=qz[j-1];//难点
if(ss.s[i]==ss.s[j]) j++;
qz[i]=j;
ss.next[i]=qz[i];
if(ss.s[i+1]==ss.s[qz[i]])
ss.next_val[i]=ss.next_val[ss.next[i]-1];
else
ss.next_val[i]==ss.next[i];
}
}
int KMP(node s1,node s2){
int i=0,j=0;
while(i<s1.len&&j<s2.len){//难点
if(j==-1||s1.s[i]==s2.s[j]){
i++;
j++;
}
else j=s2.next_val[j-1];
}
if(j>=s2.len) return i-s2.len;
else return -1;
}
int main(){
cin>>s1.s>>s2.s;//s1为主串,s2为模式串
s1.len=s1.s.size();
s2.len=s2.s.size();
get_next(s2);//求模式串的next_val数组
ans=KMP(s1,s2);
cout<<ans;
}
Manacher 马拉车算法
简介
用于找最长回文串。时间复杂度 \(O(n)\)。
朴素暴力找最长回文串是 \(O(n^2)\) 的。我们利用回文串的对称性，考虑顺序处理以每个位置为中心的回文串，为方便使每个中心是整数，可以在相邻字符间插入一个特殊字符，例如 #。数组 \(p_i\) 记录以 \(i\) 为中心的最长回文串半径。维护一个 \(r\) 表示当前处理完的回文串到达的最右边的位置，\(mid\) 表示最右边的回文串的中心。处理以 \(i\) 为中心的回文串时，把 \(i\) 关于 \(mid\) 对称得到 \(i'\)，如果 \(i\le r\)，由于对称性，\(i'\) 右侧一段会和 \(i\) 左侧相同，\(i'\) 左侧会有一段和 \(i\) 右侧相同，因此 \(p_i\) 可以直接继承继承 \(p_{i'}\) 但是要注意边界处理。然后我们可以暴力往 \(r\) 的右边扩展 \(p_i\)，由于 \(r\) 最多扩展 \(n\) 次，所以这样的暴力也是 \(O(n)\) 次的。
Code
#include <bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
using namespace std;
typedef long long ll;
const int N = 1.1e7+7;
char c[N<<1];
int n,ans;
inline void read() {
char ch=getchar();
c[0]='$',c[n=1]='#';
for(;ch<'a'||ch>'z';ch=getchar());
for(;ch>='a'&&ch<='z';ch=getchar()) c[++n]=ch,c[++n]='#';
c[++n]='@';
}
int p[N<<1];
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#endif
read();
int mid=0,r=0;
rep(i,1,n){
if(i<=r) p[i]=min(p[(mid<<1)-i],r-i+1);
while(c[i-p[i]]==c[i+p[i]]) p[i]++;
if(p[i]+i>r) r=p[i]+i-1,mid=i;
ans=max(ans,p[i]);
}
pf("%d\n",ans-1);
}
trie 字典树
code
给出一棵普通字典树的代码：
#include <bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
using namespace std;
typedef long long ll;
const int N=1e5+7,M=3e6+5;
int t,n,q;
char s[M];
int hs(char c){
if(c>='0'&&c<='9') return c-'0';
else if(c>='A'&&c<='Z') return c-'A'+10;
else return c-'a'+36;
}
struct trie{
int sum;
int cnt[M];
int ch[M][65];
void clear() {
rep(i,0,sum) {
memset(ch[i],0,sizeof(ch[i]));
cnt[i]=0;
}
sum=0;
}
void insert(char s[]){
int p=0,len=strlen(s);
rep(i,0,len-1){
int c=hs(s[i]);
if(!ch[p][c]) ch[p][c]=++sum;
p=ch[p][c];
cnt[p]++;
}
}
int ask(char s[]){
int p=0,len=strlen(s);
rep(i,0,len-1){
int c=hs(s[i]);
if(!ch[p][c]) return 0;
p=ch[p][c];
}
return cnt[p];
}
}tr;
int main() {
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("my.out","w",stdout);
#endif
sf("%d",&t);
while(t--){
tr.clear();
sf("%d%d",&n,&q);
rep(i,1,n) {
sf("%s",s);
tr.insert(s);
}
rep(i,1,q){
sf("%s",s);
int ans=tr.ask(s);
pf("%d\n",ans);
}
}
}