1 第9章 串与序列的算法2学习要点3子串搜索算法子串搜索，又称串匹配，是关于串的最重要的基本运算之一。对于给定的长度为n的主串t和
长度为m的模式串p，子串搜索运算就是找出p在t中出现的位置。简单子串搜索算法的基本思想是：从主串t的第一个字符起和模式串p的第1个
字符进行比较。若相等则继续逐个比较后续字符，否则从t的第2个字符起继续和p的第1个字符进行比较。依此类推，直至p中的每个字符依次和
t中的一个子串中字符相等。此时搜索成功，否则称搜索失败。简单子串搜索算法int naive(const string& t,con
st string& p){// 简单子串搜索算法 n=t.length(); m=p.length(); int i=0;
while(i<=n-m){ int j=0; while(j if(j==m) return i; i++; } return -1;}45KMP算法6int KMP-Matche
r(const string& t,const string& p){// KMP算法 n=t.length(); m=p.l
ength(); build(p,next); int j=-1; for (int i=0;i ile(j>-1 && p[j+1]!=t[i])j=next[j]; if(p[j+1]==t[i])j++; if
(j==m-1)return i-m+1; } return -1;}7void build(const string& p,
int next){// 计算前缀函数 next[0]=-1; int j=-1; for(int i=1;
i<=m-1;i++){ while(j>-1 && p[j+1]!=p[i])j=next[j];
if(p[j+1]==p[i])j++; next[i]=j; }}8Rabin-Karp算法long has
h(const string& p,int i,int m){// 计算子串的散列值 long h=0; for(in
t j=0;j t string& t,const string& p){// Rabin-Karp算法 int m=p.length();
int n=t.length(); long hp=hash(p,0,m); for(int i=0;i<=n
-m;i++){ long ht=hash(t,i,m); if(hp==ht)return i;
} return n;}10int Rabin_Karp(const string& t,const string& p
){// Rabin-Karp子串搜索算法 int m=p.length(); int n=t.length();
if(n ); long rm=1; for(int i=1;i -1) % q if((hp==ht) && check(t,p,0,m))return 0; // 检测散列匹配;
然后检测精确匹配 for(int i=m;i -rmt[i-m]%q)%q; ht=(htr+t[i])%q; // 匹配 int
offset=i-m+1; if((hp==ht) && check(t,p,offset,m))return o
ffset; } // 不匹配 return n;}11多子串搜索与AC自动机AC自动机的转向(goto)函数1
2AC自动机的失败函数和输出函数13AC自动机的状态结点typedef struct node{// AC自动机的状态结点 in
t cnt; int state; node fail; node go[dsize]; vector g> output;}tnode;14void insert(const string& word){// 插入关键词树 t
node cur=root; for(int i=0;i r->go[idx[word[i]]])cur->go[idx[word[i]]]=newnode(); cur=cu
r->go[idx[word[i]]]; } cur->output.push_back(word); cur-
>cnt=1;}15void build_failure(){// 计算失败函数 queue q; root-
>fail=NULL; q.push(root); while(!q.empty()){ tnode cur=q.fr
ont(); q.pop(); for(int i=0;igo[i]
){ tnode p=cur->fail; while(p && !p->go[i])p=p->fa
il; if(p){ cur->go[i]->fail=p->go[i]; cu
r->go[i]->cnt=addout(cur->go[i],p->go[i]); } q.push
(cur->go[i]); } else cur->go[i]=cur==root?root:cur->fai
l->go[i]; }}16int mult_search(const string& text){// AC自动机多子串搜索
int cnt=0; tnode cur=root; for(int i=0;i ++i) if(cur->go[idx[text[i]]]!=root){ cur=cur->
go[idx[text[i]]]; if(cur->cnt)cnt+=cur->cnt,outout(cur
); } return cnt;}17后缀数组与最长公共子串18后缀数组1920class suffix{//
后缀数组类 private: string t,suff; int n,sa; public: su
ffix(string txt){ n=txt.length(); t=new string[n];suff=
new string[n];sa=new int[n]; for(int i=0;i ; for(int i=0;i nt i=0;i +)text+=t[j]; suff[i]=text; } for(int i=1,j;i i++){ string key=suff[i]; int idx=sa[i]; for
(j=i-1;j>=0;j--) if(suff[j].compare(key)>0){
suff[j+1]=suff[j];sa[j+1]=sa[j]; } else break;
suff[j+1]=key;sa[j+1]=idx; } }};21后缀数组的倍前缀算法 void
doubling(int t){// 构造后缀数组的倍前缀算法 int x=a,y=b; for(int i=0;i ;i++)x[i]=t[i],y[i]=i; radix(x,y,sa,n,m); for(int h=1;h { sort2(x,y,h); swap(x,y);x[sa[0]]=0;m=1; for(int i=1;i<
n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],h)?m-1:m++; }}22void radix(in
t x,int y,int z,int n,int m){// 根据y的序将x排序为z for(int i=0;i ++) cnt[i]=0; for(int i=0;i nt i=1;i=0;i--) z[--cn
t[x[y[i]]]]=y[i];// 排序}23void sort2(int x,int y,int h){// 对2元序列
对序列排序 int t=0; for(int i=n-h;i n;i++) if(sa[i]>=h) y[t++]=sa[i]-h; radix(x,y,sa,n,m);}24后缀数组的DC
3分治法void dc3(int t,int sa,int n,int m){// 构造后缀数组的DC3分治法 int t
12=t+n,sa12=sa+n,a0=(n+2)/3,a1=(n+1)/3,a12=a1+n/3; t[n]=t[n+1]=
0; int p=divide(t,sa,t12,n,m,a1,a12); conquer(t,sa12,t12,n,m,p,
a1,a12); merge(t,sa,sa12,n,m,a0,a1,a12); return;}25int divide(i
nt t,int sa,int t12,int n,int m,int a1,int a12){// 非对称分割 int
d=0; for(int i=0;i 2,m); radix(t+1,b,a,a12,m); radix(t,a,b,a12,m); d=1;t12[add1(b
[0])]=0; for(int i=1;i b[i])?d-1:d++; return d;}26void conquer(int t,int sa12,int t1
2,int n,int m,int p,int a1,int a12){// 递归后缀排序 int i,a0=0; if(p<
a12) dc3(t12,sa12,a12,p); else for(i=0;i ; for(i=0;i 1) b[a0++]=n-1; radix(t,b,a,a0,m);}27void merge(int t,int sa,i
nt sa12,int n,int m,int a0,int a1,int a12){// 后缀合并 int i,j,p;
for(i=0;i ]=i; for(i=0,j=0,p=0;i [i],b[j])?a[i++]:b[j++]; for(;i 2;p++) sa[p]=b[j++];}28最长公共前缀与最长公共扩展算法void kasai(int t,int sa,i
nt n){// 构造最长公共前缀数组lcp int k=0;sa[n]=n; for(int i=0;i k[sa[i]]=i; for(int i=0;i le(i+k (k>0)k--; }}29int lce(int l,int r,int n){// 最长公共扩展 if(l==r)retu
rn(n-l); return rmq(min(rank[l],rank[r]),max(rank[l],rank[r]));}
30int rmq(int low,int high){// 区间最小查询 int v=lcp[low]; for(int i
=low+1;i lcss(string s1,string s2){// 最长公共子串算法 int sa,lcp,m,n,ans=0; s
tring t; m=s1.length();n=s1.length()+s2.length(); change(s1,s2,
t); suffix suf(t);sa=suf.sa;lcp=suf.lcp; for(int i=0;i if(lcp[i]>ans && diff(sa,m,i))ans=lcp[i]; return ans;}32void
change(string s1,string s2,string& t){// 字符串变换 int m=s1.length(
),n=s2.length(); t.resize(n+m+1); for(int i=0;i ]; for(int i=0;i 辑距离算法34int ed(){// 编辑距离的动态规划算法 for(int i=0;i<=n;i++)d[i][0]=i;
for(int i=0;i<=m;i++)d[0][i]=i; for(int i=0;i j=0;j [i+1][j+1]=min(d[i][j]+dt,min(d[i][j+1],d[i+1][j])+1); return d[
n][m];}35void back(int i,int j){// 构造最优编辑序列 if(i==0 || j==0) ret
urn; if(x[i-1]==y[j-1])back(i-1,j-1); else if(d[i-1][j-1]+dt n(d[i-1][j],d[i][j-1])+1){ back(i-1,j-1); cout<<"r("< ","< 1,j); cout<<"d("< cout<<"i("< 1,0,sizeof d1); int oldd,newd; for(int i=0;i<=n;i++) for(in
t j=0;j<=m;j++){ if(i==0)oldd=d1[j],d1[j]=j; else if(j==0
)oldd=d1[j],d1[j]=i; else{ if(x[i-1]==y[j-1])newd=oldd; else newd=min(oldd+dt,min(d1[j-1],d1[j])+1); oldd=d1[j],d1[j]=newd; } } return d1[m];}37最长公共单调子序列38int lcis(){// 最长公共递增子序列 memset(f,0,sizeof(f)); for(int i=1;i<=n;i++){ int max=0; for(int j=1;j<=m;j++){ f[i][j]=f[i-1][j]; if(x[i-1]>y[j-1] && max
|
|
