Trie
这个…不想写了
KMP
朴素的对比字符串算法复杂度是O(mn)的.这样一来对两串比较长的字符串就显得略微低效了.
KMP算法的时间复杂度也不过O(m+n)
Next数组
对于KMP而言最重要的莫过于这个Next数组了.
Next数组最大的作用在于当匹配失败时,需要跳转到哪个下标.
构造方法:
Next[i]=max{j | j\<i 且N[1..j]=N[i-j+1..i]}
即Next[i]球的试串P[1..i]的一个最长的前缀P[1..j],这个前缀同时也是他的后缀。当这个前缀找不到的时候,Next[i]=0
例如:
模式串 P = ababc
则Next[4]=2,因为ab不仅是abab的前缀,也是他的后缀.
而Next[5]=0，因为无法找到ababc(P[1..5])的一个前缀同时又是他的后缀.
附上一张图
匹配时逻辑
KMP 在匹配时同时维护两个下标 i 和 j ,表示当前模式串 P 的前 j 个字符与主串 T 在位置 i 前的 j 个字符匹配,即 P[1..j]=T[i-j..i-1]。
当算法尝试对 T[i] 和 P[j+1] 匹配中遇到不相同的字符,就会通过Next数组进行跳跃。
算法实现
Next数组
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+7;
int Next[maxn];
string S,T;//S主串,T子串
void getNext(){
int k=-1,len=T.length();
int j=0;
Next[0]=-1;
while(j<len){
//如果有相同前缀
if(k==-1 || T[j]==T[k]) Next[++j]=++k;
else k=Next[k];
}
}
void print(){
for(int i=0;i<T.length();++i){
cout<<Next[i]<<" ";
}
cout<<endl;
}
int main(){
while(cin>>T){
getNext();
print();
}
return 0;
}
几组数据
ababc
Next: -1 0 0 1 2
abcdef
Next: -1 0 0 0 0 0
abcdabce
Next: -1 0 0 0 0 1 2 3
abcabcabc
Next: -1 0 0 0 1 2 3 4 5
abcdabcabcd
Next: -1 0 0 0 0 1 2 3 1 2 3
KMP – 返回第一个匹配的下标
主程
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+7;
int Next[maxn];
string S,T;//S主串,T子串
void getNext(){
int k=-1,len=T.length();
int j=0;
Next[0]=-1;
while(j<len){
//如果有相同前缀
if(k==-1 || T[j]==T[k]) Next[++j]=++k;
else k=Next[k];
}
}
void print(){
for(int i=0;i<T.length();++i){
cout<<Next[i]<<" ";
}
cout<<endl;
}
int KMP_index(){
int i=0,j=0,slen=S.length(),tlen=T.length();
getNext();
while(i<slen && j<tlen){
if(j==-1 || S[i]==T[j]){
i++;
j++;
}else j=Next[j];
}
if(j==tlen) return i-tlen;
else return -1;
}
int main(){
while(cin>>S>>T){
int ans=KMP_index();
if(ans==-1) cout<<"Failed!"<<endl;
else cout<<"Succesed!String T was matched in index "<<ans<<"."<<endl;
print();
}
return 0;
}
两组数据
IN[0]: jashdjashdjabababcabcsdas
IN[1]: abcabc
OUT[0]: Succesed!String T was matched in index 15.
OUT[1]: -1 0 0 0 1 2
IN[2]: jashdjashdjabababcabcsdas
IN[3]: abcabcd
OUT[2]: Failed!
OUT[3]: -1 0 0 0 1 2 3
AC-Corasick 自动机
思想是KMP+Trie,在Trie上建立失配指针.
常用于主串匹配多个字符串
尾节点记录字符串下标的AC自动机
优点是可以直接输出字符串.
#include<bits/stdc++.h>
using namespace std;
const int maxn=(int)500005;
const int max_tot=(int)1e6+6;
int T,N;
char str[10010][60],tot[max_tot];
struct AC_AutoMaton{
static const int sigma_size=26;
static const char first_caractar='a';
///Trie树
int ch[maxn][sigma_size];
///后缀相关数组
int f[maxn],last[maxn];
///个数信息,尾节点记录信息
int cnt[maxn],val[maxn];
///总节点个数
int siz;
int all_su;///记录总共有多少不可重复子串
void init(){
siz=all_su=0;
memset(ch,0,sizeof(ch));
memset(val,0,sizeof(val));
}
int ord(char c){
return c-first_caractar;
}
void insert(char *s,int v){
int u=0,n=strlen(s);
for(int i=0;i<n;++i){
int c=ord(s[i]);
if(!ch[u][c]) ch[u][c]=++siz;
u=ch[u][c];
}
///尾节点记录字符串在str数组的下标
val[u]=v;
}
//Fail树
void getFail(){
queue<int> Q;
f[0]=0;
///遍历取出第一个节点所有的前向字符
for(int c=0;c<sigma_size;++c){
int u=ch[0][c];
if(u){
f[u]=last[u]=0;
Q.push(u);
}
}
while(!Q.empty()){
int k=Q.front();
Q.pop();
for(int c=0;c<sigma_size;++c){
int u=ch[k][c];
if(!u) continue;
Q.push(u);
int v=f[k];
while(v && !ch[v][c]) v=f[v];
f[u]=ch[v][c];
last[u]=val[f[u]]?f[u]:last[f[u]];
}
}
}
///统计
void add(int u){
for(;u;u=last[u]){
if(!cnt[val[u]]) all_su++;
printf("\n%s\n",str[val[u]-1]);
cnt[val[u]]++;
}
}
///多模式匹配
void Find(char *s){
int u=0,n=strlen(s);
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;++i){
int c=ord(s[i]);
while(u && !ch[u][c]) u=f[u];
u=ch[u][c];
if(val[u]) add(u);
else if(last[u]) add(last[u]);
}
}
}aho;
int main(){
scanf("%d",&T);
while(T--){
aho.init();
scanf("%d",&N);
for(int i=0;i<N;++i){
scanf("%s",str[i]);
aho.insert(str[i],i+1);
}
aho.getFail();
scanf("%s",tot);
aho.Find(tot);
printf("%d\n",aho.all_su);
}
return 0;
}
尾节点记录可重复子串在总串中出现次数
#include<bits/stdc++.h>
using namespace std;
const int maxn=(int)500005;
const int max_tot=(int)1e6+6;
int T,N;
char str[10010][60],tot[max_tot];
struct AC_AutoMaton{
static const int sigma_size=26;
static const char first_caractar='a';
int ch[maxn][sigma_size];
int f[maxn],last[maxn];
int cnt[maxn],val[maxn];
int siz;
int ans;
void init(){
siz=ans=0;
memset(ch,0,sizeof(ch));
memset(val,0,sizeof(val));
}
int ord(char c){
return c-first_caractar;
}
void insert(char *s){
int u=0,n=strlen(s);
for(int i=0;i<n;++i){
int c=ord(s[i]);
if(!ch[u][c]) ch[u][c]=++siz;
u=ch[u][c];
}
///表示以第u棵节点为字符串最后一个字符节点的个数
///如果想存储该节点代表的是哪个字符串.即存储该字符串的下标
///val[u]=v;(v是下标)
///但是这样存储就会出现无法统计之前有多少个重复字符串
///比如这道题如果输入
///3
///sha
///sha
///sha
///shashasha
///则用第一种方法最后结果是3
///但用第二种方法只能匹配一次sha
val[u]++;
}
//Fail树
void getFail(){
queue<int> Q;
f[0]=0;
///遍历取出第一个节点所有的前向字符
for(int c=0;c<sigma_size;++c){
int u=ch[0][c];
if(u){
f[u]=last[u]=0;
Q.push(u);
}
}
while(!Q.empty()){
int k=Q.front();
Q.pop();
for(int c=0;c<sigma_size;++c){
int u=ch[k][c];
if(!u) continue;
Q.push(u);
int v=f[k];
while(v && !ch[v][c]) v=f[v];
f[u]=ch[v][c];
last[u]=val[f[u]]?f[u]:last[f[u]];
}
}
}
///统计
void add(int u){
if(u){
if(!cnt[u]) ans+=val[u],cnt[u]=1;
add(last[u]);
}
}
///多模式匹配
void Find(char *s){
int u=0,n=strlen(s);
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;++i){
int c=ord(s[i]);
while(u && !ch[u][c]) u=f[u];
u=ch[u][c];
if(val[u]) add(u);
else if(last[u]) add(last[u]);
}
}
}aho;
int main(){
scanf("%d",&T);
while(T--){
aho.init();
scanf("%d",&N);
for(int i=0;i<N;++i){
scanf("%s",str[i]);
aho.insert(str[i]);
}
aho.getFail();
scanf("%s",tot);
aho.Find(tot);
printf("%d\n",aho.ans);
}
return 0;
}
失配函数优化
接下来都基于第一个代码进行优化,可以复刻到第二个代码上
即将失配记录转变成 一条确定的边连到Trie中(这样应该就不能被称之为树了)
if(!u) continue; =>
if(!u) {ch[k][c]=ch[f[k]][c];continue;}
删掉适配函数BFS中的 while()
#include<bits/stdc++.h>
using namespace std;
const int maxn=(int)500005;
const int max_tot=(int)1e6+6;
int T,N;
char str[10010][60],tot[max_tot];
struct AC_AutoMaton{
static const int sigma_size=26;
static const char first_caractar='a';
///Trie树
int ch[maxn][sigma_size];
///后缀相关数组
int f[maxn],last[maxn];
///个数信息,尾节点记录信息
int cnt[maxn],val[maxn];
///总节点个数
int siz;
int all_su;///记录总共有多少不可重复子串
void init(){
siz=all_su=0;
memset(ch,0,sizeof(ch));
memset(val,0,sizeof(val));
}
int ord(char c){
return c-first_caractar;
}
void insert(char *s,int v){
int u=0,n=strlen(s);
for(int i=0;i<n;++i){
int c=ord(s[i]);
if(!ch[u][c]) ch[u][c]=++siz;
u=ch[u][c];
}
///尾节点记录字符串在str数组的下标
val[u]=v;
}
//Fail树
void getFail(){
queue<int> Q;
f[0]=0;
///遍历取出第一个节点所有的前向字符
for(int c=0;c<sigma_size;++c){
int u=ch[0][c];
if(u){
f[u]=last[u]=0;
Q.push(u);
}
}
while(!Q.empty()){
int k=Q.front();
Q.pop();
for(int c=0;c<sigma_size;++c){
int u=ch[k][c];
if(!u) {ch[k][c]=ch[f[k]][c];continue;}
Q.push(u);
int v=f[k];
f[u]=ch[v][c];
last[u]=val[f[u]]?f[u]:last[f[u]];
}
}
}
///统计
void add(int u){
for(;u;u=last[u]){
if(!cnt[val[u]]) all_su++;
printf("\n%s\n",str[val[u]-1]);
cnt[val[u]]++;
}
}
///多模式匹配
void Find(char *s){
int u=0,n=strlen(s);
memset(cnt,0,sizeof(cnt));
for(int i=0;i<n;++i){
int c=ord(s[i]);
while(u && !ch[u][c]) u=f[u];
u=ch[u][c];
if(val[u]) add(u);
else if(last[u]) add(last[u]);
}
}
}aho;
int main(){
scanf("%d",&T);
while(T--){
aho.init();
scanf("%d",&N);
for(int i=0;i<N;++i){
scanf("%s",str[i]);
aho.insert(str[i],i+1);
}
aho.getFail();
scanf("%s",tot);
aho.Find(tot);
printf("%d\n",aho.all_su);
}
return 0;
}
MLE和TLE优化–内存优化
听说之前网络赛的时候就有道AC自动机的题,然后普通的模板总是MLE.
少了一半的时间,一半的内存
意在每次不全初始化,每多一个节点初始化一次
#include<bits/stdc++.h>
using namespace std;
const int maxn=(int)500005;
const int max_tot=(int)1e6+6;
int T,N;
char str[60],tot[max_tot];
struct AC_AutoMaton{
static const int sigma_size=26;
static const char first_caractar='a';
///Trie树
int ch[maxn][sigma_size];
///后缀相关数组fail,last
int f[maxn];
///个数信息,尾节点记录信息
int cnt[maxn],val[maxn];
///总节点个数,根节点编号
int siz,root;
int ans;
int newNode(){
memset(ch[siz],0,sizeof(ch[siz]));
f[siz]=val[siz]=0;
return siz++;
}
void init(){
ans=0;siz=0;root=newNode();
}
int ord(char c){
return c-first_caractar;
}
void insert(char *s){
int u=root,n=strlen(s);
for(int i=0;i<n;++i){
int c=ord(s[i]);
if(!ch[u][c]) ch[u][c]=newNode();
u=ch[u][c];
}
val[u]++;
}
//Fail树,build
void getFail(){
queue<int> Q;
Q.push(root);
while(!Q.empty()){
int k=Q.front();
Q.pop();
for(int c=0;c<sigma_size;++c){
if(ch[k][c]){
f[ch[k][c]]=k?ch[f[k]][c]:0;
Q.push(ch[k][c]);
}
else ch[k][c]=ch[f[k]][c];
}
}
}
///多模式匹配
void Find(char *s){
int u=0,n=strlen(s);
for(int i=0;i<n;++i){
int c=ord(s[i]);
u=ch[u][c];
int p=u;
while(p && val[p]){
ans+=val[p];
val[p]=0;
p=f[p];
}
}
}
}aho;
int main(){
scanf("%d",&T);
while(T--){
aho.init();
scanf("%d",&N);
for(int i=0;i<N;++i){
scanf("%s",str);
aho.insert(str);
}
aho.getFail();
scanf("%s",tot);
aho.Find(tot);
printf("%d\n",aho.ans);
}
return 0;
}
但是以上自动机识别形如a,ab,abc,abcd这类子串会出问题,在刷题时发现的,下面重新用新的方法来解决这个问题,建议用下面的AC自动机
HDU 2222，上面的那些题,修改
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+6;
int T,N,tot_len;
char str[maxn],len[maxn];
struct AC_AutoMaton{
static const int sigma_size=26;
int ch[maxn][sigma_size];
int f[maxn];
int cle[maxn],val[maxn];
int siz,root,ans;
int newNode(){
for(int i=0;i<sigma_size;++i){
ch[siz][i]=0;
}
f[siz]=val[siz]=0;
return siz++;
}
void init(){
for(int i=0;i<maxn;++i) val[i]=0;
ans=0;
siz=0;root=0;
newNode();
}
int ord(char c){
if(isupper(c))
c=tolower(c);
return (int)(c-'a');
}
void insert(char *s){
int u=root,n=strlen(s);
for(int i=0;i<n;++i){
int c=ord(s[i]);
if(!ch[u][c]) ch[u][c]=newNode();
u=ch[u][c];
}
val[u]++;
}
void getFail(){
queue<int> Q;
Q.push(root);
while(!Q.empty()){
int k=Q.front();
Q.pop();
for(int c=0;c<sigma_size;++c){
if(ch[k][c]){
f[ch[k][c]]=k?ch[f[k]][c]:0;
Q.push(ch[k][c]);
}
else ch[k][c]=ch[f[k]][c];
}
}
}
void add(int u,int i){
while(u){
if(val[u]){
int t=len[val[u]];
for(int r=0;r<t;++r){
cle[i-r]=1;
}
return;
}
u=f[u];
}
}
void Find(char *s){
int u=0,n=tot_len;
for(int i=0;i<tot_len;++i) cle[i]=0;
for(int i=0;i<n;++i){
int c=ord(s[i]);
///下面这句加不加都一样
//while(u && !ch[u][c]) u=f[u];
u=ch[u][c];
int p=u;
while(p && val[p]){
ans+=val[p];
val[p]=0;
p=f[p];
}
}
}
}aho;
int main(){
scanf("%d",&T);
while(T--){
aho.init();
scanf("%d",&N);
for(int i=0;i<N;++i){
scanf("%s",str);
aho.insert(str);
len[i+1]=strlen(str);
}
getchar();
aho.getFail();
tot_len=0;
gets(str);
tot_len=strlen(str);
aho.Find(str);
printf("%d\n",aho.ans);
}
return 0;
}
HDU 5880,青岛区域赛网赛
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+6;
int T,N,tot_len;
char str[maxn],len[maxn];
struct AC_AutoMaton{
static const int sigma_size=26;
int ch[maxn][sigma_size];
int f[maxn];
int cle[maxn],val[maxn];
int siz,root;
int newNode(){
for(int i=0;i<sigma_size;++i){
ch[siz][i]=0;
}
f[siz]=val[siz]=0;
return siz++;
}
void init(){
for(int i=0;i<maxn;++i) val[i]=0;
siz=0;root=0;
newNode();
}
int ord(char c){
if(isupper(c))
c=tolower(c);
return (int)(c-'a');
}
void insert(char *s,int v){
int u=root,n=strlen(s);
for(int i=0;i<n;++i){
int c=ord(s[i]);
if(!ch[u][c]) ch[u][c]=newNode();
u=ch[u][c];
}
val[u]=v;
}
void getFail(){
queue<int> Q;
Q.push(root);
while(!Q.empty()){
int k=Q.front();
Q.pop();
for(int c=0;c<sigma_size;++c){
if(ch[k][c]){
f[ch[k][c]]=k?ch[f[k]][c]:0;
Q.push(ch[k][c]);
}
else ch[k][c]=ch[f[k]][c];
}
}
}
void add(int u,int i){
while(u){
if(val[u]){
int t=len[val[u]];
for(int r=0;r<t;++r){
cle[i-r]=1;
}
return;
}
u=f[u];
}
}
void Find(char *s){
int u=0,n=tot_len;
for(int i=0;i<tot_len;++i) cle[i]=0;
for(int i=0;i<n;++i){
if(!isalpha(s[i])){
u=0;
continue;
}
int c=ord(s[i]);
///下面这句加不加都一样
//while(u && !ch[u][c]) u=f[u];
u=ch[u][c];
/*
int p=u;
//cout<<i<<" "<<u<<": "<<c<<endl;
///while是用来判断子串的.这道题不需要加
while(p && val[p]){
p=f[p];
}
*/
add(u,i);
}
}
void print(){
for(int i=0;i<tot_len;++i){
if(cle[i]) putchar('*');
else putchar(str[i]);
}
printf("\n");
}
}aho;
int main(){
scanf("%d",&T);
while(T--){
aho.init();
scanf("%d",&N);
for(int i=0;i<N;++i){
scanf("%s",str);
aho.insert(str,i+1);
len[i+1]=strlen(str);
}
getchar();
aho.getFail();
tot_len=0;
//scanf("%[^\n]",str);
gets(str);
tot_len=strlen(str);
//cout<<tot_len<<endl;
aho.Find(str);
aho.print();
}
return 0;
}
后缀数组
后缀自动机
