1、1 第9章 串与序列的算法2学习学习要点要点 理解串的基本概念。掌握子串搜索的常用算法。掌握构造后缀数组的算法及应用。掌握比较序列的高效算法。理解串的基本概念。掌握子串搜索的常用算法。掌握构造后缀数组的算法及应用。掌握比较序列的高效算法。3子子串搜索算法串搜索算法n子串搜索，又称串匹配，是关于串的最重要的基本运算之一。n对于给定的长度为n的主串t和长度为m的模式串p，子串搜索运算就是找出p在t中出现的位置。n简单子串搜索算法的基本思想是：从主串t的第一个字符起和模式串p的第1个字符进行比较。若相等则继续逐个比较后续字符，否则从t的第2个字符起继续和p的第1个字符进行比较。依此类推，直至p中的每
2、个字符依次和t中的一个子串中字符相等。此时搜索成功，否则称搜索失败。简单简单子串搜索算法子串搜索算法nint naive(const string&t,const string&p)n/简单子串搜索算法n n=t.length();n m=p.length();n int i=0;n while(i=n-m)n int j=0;n while(jm&ti+j=pj)j+;n if(j=m)return i;n i+;n n return-1;n45KMPKMP算法算法6nint KMP-Matcher(const string&t,const string&p)n/KMP算法n n=t.len
3、gth();n m=p.length();n build(p,next);n int j=-1;n for(int i=0;i-1&pj+1!=ti)j=nextj;n if(pj+1=ti)j+;n if(j=m-1)return i-m+1;n n return-1;n7nvoid build(const string&p,int*next)n/计算前缀函数n next0=-1;n int j=-1;n for(int i=1;i-1&pj+1!=pi)j=nextj;n if(pj+1=pi)j+;n nexti=j;n n8Rabin-Karp算法算法nlong hash(const
4、string&p,int i,int m)n/计算子串的散列值n long h=0;n for(int j=0;jm;j+)h=(r*h+pi+j)%q;n return h;n9nint Rabin_Karp(const string&t,const string&p)n/Rabin-Karp算法n int m=p.length();n int n=t.length();n long hp=hash(p,0,m);n for(int i=0;i=n-m;i+)n long ht=hash(t,i,m);n if(hp=ht)return i;n n return n;n10nint Rabi
5、n_Karp(const string&t,const string&p)n/Rabin-Karp子串搜索算法n int m=p.length();n int n=t.length();n if(nm)return n;n long ht=hash(t,0,m);n long hp=hash(p,0,m);n long rm=1;n for(int i=1;im;i+)rm=(r*rm)%q;/计算 r(m-1)%q n if(hp=ht)&check(t,p,0,m)return 0;n /检测散列匹配;然后检测精确匹配n for(int i=m;in;i+)n /检测匹配n ht=(ht+
6、q-rm*ti-m%q)%q;n ht=(ht*r+ti)%q;n /匹配n int offset=i-m+1;n if(hp=ht)&check(t,p,offset,m)return offset;n n /不匹配n return n;n11多子串搜索与多子串搜索与ACAC自动机自动机nAC自动机的转向(goto)函数12nAC自动机的失败函数和输出函数13nAC自动机的状态结点ntypedef struct noden/AC自动机的状态结点n int cnt;n int state;n node*fail;n node*godsize;n vector output;ntnode;14n
7、void insert(const string&word)n/插入关键词树n tnode*cur=root;n for(int i=0;igoidxwordi)cur-goidxwordi=newnode();n cur=cur-goidxwordi;n n cur-output.push_back(word);n cur-cnt=1;n15nvoid build_failure()n/计算失败函数n queue q;n root-fail=NULL;n q.push(root);n while(!q.empty()n tnode*cur=q.front();n q.pop();n for(
8、int i=0;igoi)n tnode*p=cur-fail;n while(p&!p-goi)p=p-fail;n if(p)n cur-goi-fail=p-goi;n cur-goi-cnt=addout(cur-goi,p-goi);n n q.push(cur-goi);n n else cur-goi=cur=root?root:cur-fail-goi;n n16nint mult_search(const string&text)n/AC自动机多子串搜索n int cnt=0;n tnode*cur=root;n for(int i=0;igoidxtexti!=root)n
9、 cur=cur-goidxtexti;n if(cur-cnt)cnt+=cur-cnt,outout(cur);n n return cnt;n17后缀数组与最长公共子串后缀数组与最长公共子串18n后缀数组1920nclass suffixn/后缀数组类n private:n string*t,*suff;n int n,*sa;n public:n suffix(string txt)n n=txt.length();n t=new stringn;suff=new stringn;sa=new intn;n for(int i=0;in;i+)ti=txti;n for(int i=0
10、;in;i+)sai=i;n n void build()n for(int i=0;in;i+)n string text=;n for(int j=i;jn;j+)text+=tj;n suffi=text;n n for(int i=1,j;i=0;j-)n if(pare(key)0)n suffj+1=suffj;saj+1=saj;n n else break;n suffj+1=key;saj+1=idx;n n n;21后缀数组的倍前缀算法后缀数组的倍前缀算法n void doubling(int*t)n/构造后缀数组的倍前缀算法n int*x=a,*y=b;n for(int
11、 i=0;in;i+)xi=ti,yi=i;n radix(x,y,sa,n,m);n for(int h=1;hn;h*=2)n sort2(x,y,h);n swap(x,y);xsa0=0;m=1;n for(int i=1;in;i+)xsai=cmp(y,sai-1,sai,h)?m-1:m+;n n22nvoid radix(int*x,int*y,int*z,int n,int m)n/根据y的序将x排序为zn for(int i=0;im;i+)cnti=0;n for(int i=0;in;i+)cntxyi+;/出现次数n for(int i=1;i=0;i-)z-cntx
12、yi=yi;/排序n23nvoid sort2(int*x,int*y,int h)n/对2元序列对序列排序n int t=0;n for(int i=n-h;in;i+)yt+=i;n for(int i=0;i=h)yt+=sai-h;n radix(x,y,sa,n,m);n24后缀数组的后缀数组的DC3分治法分治法nvoid dc3(int*t,int*sa,int n,int m)n/构造后缀数组的DC3分治法n int*t12=t+n,*sa12=sa+n,a0=(n+2)/3,a1=(n+1)/3,a12=a1+n/3;n tn=tn+1=0;n int p=divide(t,s
13、a,t12,n,m,a1,a12);n conquer(t,sa12,t12,n,m,p,a1,a12);n merge(t,sa,sa12,n,m,a0,a1,a12);n return;n25nint divide(int*t,int*sa,int*t12,int n,int m,int a1,int a12)n/非对称分割n int d=0;n for(int i=0;in;i+)if(i%3!=0)ad+=i;n radix(t+2,a,b,a12,m);n radix(t+1,b,a,a12,m);n radix(t,a,b,a12,m);n d=1;t12add1(b0)=0;n
14、for(int i=1;ia12;i+)n t12add1(bi)=cmp(t,bi-1,bi)?d-1:d+;n return d;n26nvoid conquer(int*t,int*sa12,int*t12,int n,int m,int p,int a1,int a12)n/递归后缀排序n int i,a0=0;n if(pa12)dc3(t12,sa12,a12,p);n else for(i=0;ia12;i+)sa12t12i=i;n for(i=0;ia12;i+)if(sa12ia1)ba0+=sa12i*3;n if(n%3=1)ba0+=n-1;n radix(t,b,a
15、,a0,m);n27nvoid merge(int*t,int*sa,int*sa12,int n,int m,int a0,int a1,int a12)n/后缀合并n int i,j,p;n for(i=0;ia12;i+)bi=add2(sa12i);n for(i=0;ia12;i+)cbi=i;n for(i=0,j=0,p=0;ia0&ja12;p+)n sap=cmp2(bj%3,t,ai,bj)?ai+:bj+;n for(;ia0;p+)sap=ai+;n for(;ja12;p+)sap=bj+;n28最长公共前缀与最长公共扩展算法最长公共前缀与最长公共扩展算法nvoid
16、kasai(int*t,int*sa,int n)n/构造最长公共前缀数组lcpn int k=0;san=n;n for(int i=0;in;i+)ranksai=i;n for(int i=0;in;i+)n int j=saranki+1;n while(i+kn&j+k0)k-;n n29nint lce(int l,int r,int n)n/最长公共扩展n if(l=r)return(n-l);n return rmq(min(rankl,rankr),max(rankl,rankr);n30nint rmq(int low,int high)n/区间最小查询n int v=lc
17、plow;n for(int i=low+1;ihigh;i+)if(lcpiv)v=lcpi;n return v;n31最长公共子串算法最长公共子串算法nint lcss(string s1,string s2)n/最长公共子串算法n int*sa,*lcp,m,n,ans=0;n string t;n m=s1.length();n=s1.length()+s2.length();n change(s1,s2,t);n suffix suf(t);sa=suf.sa;lcp=suf.lcp;n for(int i=0;ians&diff(sa,m,i)ans=lcpi;n return
18、ans;n32nvoid change(string s1,string s2,string&t)n/字符串变换n int m=s1.length(),n=s2.length();n t.resize(n+m+1);n for(int i=0;im;i+)ti=s1i;n for(int i=0;in;i+)tm+i+1=s2i;n n=m+n+1;tm=tn=0;n33编辑距离算法编辑距离算法340,-1,(1,1)1,0-1,(1,1)1,-10,(,)(1,)1,min(,1)1,otherwise.(1,1)(,),ijd iijdjijd i jd ijd i jd ijx iy j
19、nint ed()n/编辑距离的动态规划算法n for(int i=0;i=n;i+)di0=i;n for(int i=0;i=m;i+)d0i=i;n for(int i=0;in;i+)n for(int j=0;jm;j+)n if(xi=yj)di+1j+1=dij;n else di+1j+1=min(dij+dt,min(dij+1,di+1j)+1);n return dnm;n35nvoid back(int i,int j)n/构造最优编辑序列n if(i=0|j=0)return;n if(xi-1=yj-1)back(i-1,j-1);n else if(di-1j-1
20、+dtmin(di-1j,dij-1)+1)n back(i-1,j-1);n coutr(i-1,j-1)endl;n n else if(di-1jdij-1)n back(i-1,j);n coutd(i-1)endl;n n elsen back(i,j-1);n couti(j-1)endl;n n36nint edn()n/O(n)空间算法n memset(d1,0,sizeof d1);n int oldd,newd;n for(int i=0;i=n;i+)n for(int j=0;j=m;j+)n if(i=0)oldd=d1j,d1j=j;n else if(j=0)ol
21、dd=d1j,d1j=i;n elsen if(xi-1=yj-1)newd=oldd;n else newd=min(oldd+dt,min(d1j-1,d1j)+1);n oldd=d1j,d1j=newd;n n n return d1m;n37最长公共单调子序列最长公共单调子序列38(,)0,00(,)(1,),0 1max(1,),0ijti jijf i jf iji jx iy jf iti jxynint lcis()n/最长公共递增子序列n memset(f,0,sizeof(f);n for(int i=1;i=n;i+)n int max=0;n for(int j=1;jyj-1&maxfi-1j)max=fi-1j;n if(xi-1=yj-1)fij=max+1;n n n int ret=0;n for(int i=1;i=m;i+)if(retfni)ret=fni;n return ret;n39有约束最长公共子序列有约束最长公共子序列40(1,1,1)1,(,)(1,1,)1,1max(1,),(,1,),f ijkx iy js kf i j kf ijkx iy jkf ij kf i jkx iy j
