1、1 第9章 串与序列的算法第1页，共40页。2学习学习要点要点 理解串的基本概念。掌握子串搜索的常用算法。掌握构造后缀数组的算法及应用。掌握比较序列的高效算法。理解串的基本概念。掌握子串搜索的常用算法。掌握构造后缀数组的算法及应用。掌握比较序列的高效算法。第2页，共40页。3子子串搜索算法串搜索算法n子串搜索，又称串匹配，是关于串的最重要的基本运算之一。n对于给定的长度为n的主串t和长度为m的模式串p，子串搜索运算就是找出p在t中出现的位置。n简单子串搜索算法的基本思想是：从主串t的第一个字符起和模式串p的第1个字符进行比较。若相等则继续逐个比较后续字符，否则从t的第2个字符起继续和p的第1个
2、字符进行比较。依此类推，直至p中的每个字符依次和t中的一个子串中字符相等。此时搜索成功，否则称搜索失败。第3页，共40页。简单简单子串搜索算法子串搜索算法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;n4第4页，共40页。5第5页，共40页。KMPKMP算法算法6第6页，共40页。nint KMP-
3、Matcher(const string&t,const string&p)n/KMP算法n n=t.length();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;n7第7页，共40页。nvoid 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=next
4、j;n if(pj+1=pi)j+;n nexti=j;n n8第8页，共40页。Rabin-Karp算法算法nlong hash(const 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;n9第9页，共40页。nint 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
5、 i=0;i=n-m;i+)n long ht=hash(t,i,m);n if(hp=ht)return i;n n return n;n10第10页，共40页。nint Rabin_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)%
6、q n if(hp=ht)&check(t,p,0,m)return 0;n /检测散列匹配;然后检测精确匹配n for(int i=m;in;i+)n /检测匹配n ht=(ht+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第11页，共40页。多子串搜索与多子串搜索与ACAC自动机自动机nAC自动机的转向(goto)函数12第12页，共40页。nAC自动机的失败函数和输出函数13第13页，共4
7、0页。nAC自动机的状态结点ntypedef struct noden/AC自动机的状态结点n int cnt;n int state;n node*fail;n node*godsize;n vector output;ntnode;14第14页，共40页。nvoid 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
8、;n15第15页，共40页。nvoid 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(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=
9、cur=root?root:cur-fail-goi;n n16第16页，共40页。nint mult_search(const string&text)n/AC自动机多子串搜索n int cnt=0;n tnode*cur=root;n for(int i=0;igoidxtexti!=root)n cur=cur-goidxtexti;n if(cur-cnt)cnt+=cur-cnt,outout(cur);n n return cnt;n17第17页，共40页。后缀数组与最长公共子串后缀数组与最长公共子串18第18页，共40页。n后缀数组19第19页，共40页。20nclass suf
10、fixn/后缀数组类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;in;i+)sai=i;n 第20页，共40页。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
11、 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第21页，共40页。后缀数组的倍前缀算法后缀数组的倍前缀算法n void doubling(int*t)n/构造后缀数组的倍前缀算法n int*x=a,*y=b;n for(int 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
12、=1;n for(int i=1;in;i+)xsai=cmp(y,sai-1,sai,h)?m-1:m+;n n22第22页，共40页。nvoid 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-cntxyi=yi;/排序n23第23页，共40页。nvoid sort2(int*x,int*y,int h)n/对2元序列对序列排序n int t=0;n for(int i=n-h
13、;in;i+)yt+=i;n for(int i=0;i=h)yt+=sai-h;n radix(x,y,sa,n,m);n24第24页，共40页。后缀数组的后缀数组的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,sa,t12,n,m,a1,a12);n conquer(t,sa12,t12,n,m,p,a1,a12);n merge(t,sa,sa1
14、2,n,m,a0,a1,a12);n return;n25第25页，共40页。nint 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 for(int i=1;ia12;i+)n t12add1(bi)=cmp(t,bi-1,bi)?d-1:d+;n r
15、eturn d;n26第26页，共40页。nvoid 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,a0,m);n27第27页，共40页。nvoid merge(int*t,int*sa,int*
16、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第28页，共40页。最长公共前缀与最长公共扩展算法最长公共前缀与最长公共扩展算法nvoid kasai(int*t,int*sa,int n)n/构造
17、最长公共前缀数组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 n29第29页，共40页。nint lce(int l,int r,int n)n/最长公共扩展n if(l=r)return(n-l);n return rmq(min(rankl,rankr),max(rankl,rankr);n30第30页，共40页。nint rmq(int low,int high)n/区间最小查询n int v=lcplow;n fo
18、r(int i=low+1;ihigh;i+)if(lcpiv)v=lcpi;n return v;n31第31页，共40页。最长公共子串算法最长公共子串算法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
19、 ans;n32第32页，共40页。nvoid 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第33页，共40页。编辑距离算法编辑距离算法340,-1,(1,1)1,0-1,(1,1)1,-10,(,)(1,)1,min(,1)1,otherwise.(1,1)(,),ijd iijdjijd i
20、 jd ijd i jd ijx iy j第34页，共40页。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;n35第35页，共40页。nvoid back(int i,int j)n/构造最优编辑序列n if(i=0|j=0)return;n if(
21、xi-1=yj-1)back(i-1,j-1);n else if(di-1j-1+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 n36第36页，共40页。nint 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
22、j=0;j=m;j+)n if(i=0)oldd=d1j,d1j=j;n else if(j=0)oldd=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第37页，共40页。最长公共单调子序列最长公共单调子序列38(,)0,00(,)(1,),0 1max(1,),0ijti jijf i jf iji jx iy jf iti jxy第38页，共40页。nint lcis()n/最长公共递增子序
23、列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第39页，共40页。有约束最长公共子序列有约束最长公共子序列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 第40页，共40页。
