都是从网上找的，交过题试过的应该没问题的模板。
KMP
//未优化的next函数 void getNext(char s[],int next[]) { int length=strlen(s); int i=0,j=-1; next[0]=-1; while(i<length) { if(j==-1||s[i]==s[j]) { ++i; ++j; next[i]=j; } else j=next[j]; } } //已优化的next函数 void getNextval(char s[],int nextval[]) { int length=strlen(s); int i=0,j=-1; nextval[0]=-1; while(i<length) { if(j==-1||s[i]==s[j]) { ++i; ++j; //next[i]=j; if (s[i]!=s[j]) nextval[i]=j; else nextval[i]=nextval[j]; } else j=nextval[j]; } } //KMP int KMP( char *t, char *s ) //s为主串，t为模式串 { int lenth = strlen(t); int len = strlen(s); getNextval( t, nextval ); int i = 0, j = 0; while ( j < len ) { if ( i == -1 || s[j] == t[i] ) { ++i, ++j; if ( i == lenth ) return j; } else i = nextval[i]; } return -1; }
扩展KMP
#include<iostream> #include<string> using namespace std; const int MM=100005; int next[MM],extand[MM]; char S[MM],T[MM]; void GetNext(const char *T){ int len=strlen(T),a=0; next[0]=len; while(a<len-1 && T[a]==T[a+1]) a++; next[1]=a; a=1; for(int k=2;k<len;k++){ int p=a+next[a]-1,L=next[k-a]; if( (k-1)+L >= p){ int j = (p-k+1)>0 ? (p-k+1) : 0; while(k+j<len && T[k+j]==T[j]) j++; next[k]=j; a=k; } else next[k]=L; } } void GetExtand(const char *S,const char *T){ GetNext(T); int slen=strlen(S),tlen=strlen(T),a=0; int MinLen = slen < tlen ? slen : tlen; while(a<MinLen && S[a]==T[a]) a++; extand[0]=a; a=0; for(int k=1;k<slen;k++){ int p=a+extand[a]-1, L=next[k-a]; if( (k-1)+L >= p){ int j= (p-k+1) > 0 ? (p-k+1) : 0; while(k+j<slen && j<tlen && S[k+j]==T[j]) j++; extand[k]=j; a=k; } else extand[k]=L; } } int main(){ while(scanf("%s%s",S,T)==2){ GetExtand(S,T); for(int i=0;i<strlen(T);i++) printf("%d ",next[i]); puts(""); for(int i=0;i<strlen(S);i++) printf("%d ",extand[i]); puts(""); } return 0; }
AC自动机
#include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> using namespace std; const int MAX_NODE = 1010; const int CHILD_NUM = 4; const int MAXN = 12; const int INF = 1 << 30; struct ACAutomaton { int chd[MAX_NODE][CHILD_NUM]; //每个节点的儿子,即当前节点的状态转移 int val[MAX_NODE]; //记录题目给的关键数据 int fail[MAX_NODE]; //传说中的fail指针 int Q[MAX_NODE<<1]; //队列,用于广度优先计算fail指针 int ID[128]; //字母对应的ID int sz; //已使用节点个数 //初始化,计算字母对应的儿子ID,如:'a'->0 ... 'z'->25 void Initialize() { fail[0] = 0; ID['A'] = 0; ID['G'] = 1; ID['C'] = 2; ID['T'] = 3; return; } //重新建树需先Reset void Reset() { memset(chd[0] , 0 , sizeof(chd[0])); val[0] = 0; sz = 1; } //将权值为key的字符串a插入到trie中 void Insert(char *a,int key) { int p = 0; for ( ; *a ; a ++) { int c = ID[*a]; if (!chd[p][c]) { memset(chd[sz] , 0 , sizeof(chd[sz])); val[sz] = 0; chd[p][c] = sz ++; } p = chd[p][c]; } val[p] = key; } //建立AC自动机,确定每个节点的权值以及状态转移 void Construct() { int *s = Q , *e = Q; for (int i = 0 ; i < CHILD_NUM ; i ++) { if (chd[0][i]) { fail[ chd[0][i] ] = 0; *e ++ = chd[0][i]; } } while (s != e) { int u = *s++; for (int i = 0 ; i < CHILD_NUM ; i ++) { int &v = chd[u][i]; if (v) { *e ++ = v; fail[v] = chd[ fail[u] ][i]; //以下一行代码要根据题目所给val的含义来写 val[v] |= val[ fail[v] ]; } else { v = chd[ fail[u] ][i]; } } } } } AC;
后缀数组
//rank从0开始 //sa从1开始,因为最后一个字符(最小的)排在第0位 //high从2开始,因为表示的是sa[i-1]和sa[i] #define M 220000 int rank[M],sa[M],X[M],Y[M],high[M],init[M]; int buc[M]; void calhigh(int n) { int i , j , k = 0; for(i = 1 ; i <= n ; i++) rank[sa[i]] = i; for(i = 0 ; i < n ; high[rank[i++]] = k) for(k?k--:0 , j = sa[rank[i]-1] ; init[i+k] == init[j+k] ; k++); } bool cmp(int *r,int a,int b,int l) { return (r[a] == r[b] && r[a+l] == r[b+l]); } void suffix(int n,int m = 128) { int i , l , p , *x = X , *y = Y; for(i = 0 ; i < m ; i ++) buc[i] = 0; for(i = 0 ; i < n ; i ++) buc[ x[i] = init[i] ] ++; for(i = 1 ; i < m ; i ++) buc[i] += buc[i-1]; for(i = n - 1; i >= 0 ; i --) sa[ --buc[ x[i] ]] = i; for(l = 1,p = 1 ; p < n ; m = p , l *= 2) { p = 0; for(i = n-l ; i < n ; i ++) y[p++] = i; for(i = 0 ; i < n ; i ++) if(sa[i] >= l) y[p++] = sa[i] - l; for(i = 0 ; i < m ; i ++) buc[i] = 0; for(i = 0 ; i < n ; i ++) buc[ x[y[i]] ] ++; for(i = 1 ; i < m ; i ++) buc[i] += buc[i-1]; for(i = n - 1; i >= 0 ; i --) sa[ --buc[ x[y[i]] ] ] = y[i]; for(swap(x,y) , x[sa[0]] = 0 , i = 1 , p = 1 ; i < n ; i ++) x[ sa[i] ] = cmp(y,sa[i-1],sa[i],l) ? p-1 : p++; } calhigh(n-1);//后缀数组关键是求出high,所以求sa的时候顺便把rank和high求出来 } //当需要反复询问两个后缀的最长公共前缀时用到RMQ int Log[M]; int best[20][M]; void initRMQ(int n) {//初始化RMQ for(int i = 1; i <= n ; i ++) best[0][i] = high[i]; for(int i = 1; i <= Log[n] ; i ++) { int limit = n - (1<<i) + 1; for(int j = 1; j <= limit ; j ++) { best[i][j] = min(best[i-1][j] , best[i-1][j+(1<<i>>1)]); } } } int lcp(int a,int b) {//询问a,b后缀的最长公共前缀 a = rank[a]; b = rank[b]; if(a > b) swap(a,b); a ++; int t = Log[b - a + 1]; return min(best[t][a] , best[t][b - (1<<t) + 1]); } int main() { //预处理每个数字的Log值,常数优化,用于RMQ Log[0] = -1; for(int i = 1; i <= M ; i ++) { Log[i] = (i&(i-1)) ? Log[i-1] : Log[i-1] + 1 ; } //******************************************* // n为数组长度,下标0开始 // 将初始数据,保存在init里,并且保证每个数字都比0大 // m = max{ init[i] } + 1 // 一般情况下大多是字符操作,所以128足够了 //******************************************* init[n] = 0; suffix(n+1,m); initRMQ(n); }
后缀自动机
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; #define N 2010 #define MAXQ 10010
//后缀自动机节点编号从1开始，ant为节点总数
//0号节点留作空余 struct Suffix_Automaton { int F[N << 1],ant,last,ch[N << 1][26],step[N << 1]; void init() { last = ant = 1; memset(F,0,sizeof(F)); memset(ch,0,sizeof(ch)); memset(step,0,sizeof(step)); } void ins(int x) { int t = ++ant, pa = last; step[t] = step[last] + 1; last = t; for( ; pa && !ch[pa][x]; pa = F[pa] ) ch[pa][x] = t; if( pa == 0 ) F[t] = 1; else if( step[pa] + 1 == step[ ch[pa][x] ] ) F[t] = ch[pa][x]; else { int nq = ++ant, q = ch[pa][x]; memcpy( ch[nq], ch[q], sizeof(ch[nq]) ); step[nq] = step[pa] + 1; F[nq] = F[q]; F[q] = F[t] = nq; for( ; pa && ch[pa][x] == q; pa = F[pa] ) ch[pa][x] = nq; } } };