【文档说明】计算机算法设计与分析第9章串与序列的算法课件.pptx，共(40)页，381.596 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-5412.html

以下为本文档部分文字说明：

1第9章串与序列的算法第1页，共40页。2学习要点理解串的基本概念。掌握子串搜索的常用算法。掌握构造后缀数组的算法及应用。掌握比较序列的高效算法。理解串的基本概念。掌握子串搜索的常用算法。掌握构造后缀数组的算法及应用。掌握比较序列的高效算法。第2页，共4

0页。3子串搜索算法子串搜索，又称串匹配，是关于串的最重要的基本运算之一。对于给定的长度为n的主串t和长度为m的模式串p，子串搜索运算就是找出p在t中出现的位置。简单子串搜索算法的基本思想是：从主串t的第一个字符起和模式串p的第

1个字符进行比较。若相等则继续逐个比较后续字符，否则从t的第2个字符起继续和p的第1个字符进行比较。依此类推，直至p中的每个字符依次和t中的一个子串中字符相等。此时搜索成功，否则称搜索失败。第3页，共40页。简单子串搜索算

法intnaive(conststring&t,conststring&p){//简单子串搜索算法n=t.length();m=p.length();inti=0;while(i<=n-m){intj=0;while(j<m&&t[i+j]==p[j])j++;i

f(j==m)returni;i++;}return-1;}4第4页，共40页。5第5页，共40页。KMP算法6第6页，共40页。intKMP-Matcher(conststring&t,const

string&p){//KMP算法n=t.length();m=p.length();build(p,next);intj=-1;for(inti=0;i<n;i++){while(j>-1&&p[j+1]!=t[i])j=next[j]

;if(p[j+1]==t[i])j++;if(j==m-1)returni-m+1;}return-1;}7第7页，共40页。voidbuild(conststring&p,int*next){//计算前缀函数

next[0]=-1;intj=-1;for(inti=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;}}8第8页，共40页。Rabin-Karp算

法longhash(conststring&p,inti,intm){//计算子串的散列值longh=0;for(intj=0;j<m;j++)h=(r*h+p[i+j])%q;returnh;}9第9页，共40页。intRabin_Kar

p(conststring&t,conststring&p){//Rabin-Karp算法intm=p.length();intn=t.length();longhp=hash(p,0,m);for(int

i=0;i<=n-m;i++){longht=hash(t,i,m);if(hp==ht)returni;}returnn;}10第10页，共40页。intRabin_Karp(const

string&t,conststring&p){//Rabin-Karp子串搜索算法intm=p.length();intn=t.length();if(n<m)returnn;longht=

hash(t,0,m);longhp=hash(p,0,m);longrm=1;for(inti=1;i<m;i++)rm=(r*rm)%q;//计算r^(m-1)%qif((hp==ht)&&check(t,p,0,m))return0;//检测散列匹配;然后检测精确匹配

for(inti=m;i<n;i++){//检测匹配ht=(ht+q-rm*t[i-m]%q)%q;ht=(ht*r+t[i])%q;//匹配intoffset=i-m+1;if((hp==ht)&&check(t,p,offset,m))retur

noffset;}//不匹配returnn;}11第11页，共40页。多子串搜索与AC自动机AC自动机的转向(goto)函数12第12页，共40页。AC自动机的失败函数和输出函数13第13页，共40页。AC自动机的状态结点typedefstructnode{//AC自动机的

状态结点intcnt;intstate;node*fail;node*go[dsize];vector<string>output;}tnode;14第14页，共40页。voidinsert

(conststring&word){//插入关键词树tnode*cur=root;for(inti=0;i<word.length();++i){if(!cur->go[idx[word[i

]]])cur->go[idx[word[i]]]=newnode();cur=cur->go[idx[word[i]]];}cur->output.push_back(word);cur->cnt=1;}15第15页，共40页。voidbuild_failure()

{//计算失败函数queue<tnode*>q;root->fail=NULL;q.push(root);while(!q.empty()){tnode*cur=q.front();q.pop();for(inti=0;i<dsize;++i)if(

cur->go[i]){tnode*p=cur->fail;while(p&&!p->go[i])p=p->fail;if(p){cur->go[i]->fail=p->go[i];cur->go[i]->cnt

=addout(cur->go[i],p->go[i]);}q.push(cur->go[i]);}elsecur->go[i]=cur==root?root:cur->fail->go[i];}}16第16页，共40页。intmult_search(cons

tstring&text){//AC自动机多子串搜索intcnt=0;tnode*cur=root;for(inti=0;i<text.length();++i)if(cur->go[idx[text[i]]]!=root){

cur=cur->go[idx[text[i]]];if(cur->cnt)cnt+=cur->cnt,outout(cur);}returncnt;}17第17页，共40页。后缀数组与最长公共子串18第18页，共40页。后缀数组19第19页，

共40页。20classsuffix{//后缀数组类private:string*t,*suff;intn,*sa;public:suffix(stringtxt){n=txt.length();t=newstring[n];suff=n

ewstring[n];sa=newint[n];for(inti=0;i<n;i++)t[i]=txt[i];for(inti=0;i<n;i++)sa[i]=i;}第20页，共40页。voidbuild(){for

(inti=0;i<n;i++){stringtext="";for(intj=i;j<n;j++)text+=t[j];suff[i]=text;}for(inti=1,j;i<n;i++){stringkey=suff[i];intidx=sa[i];fo

r(j=i-1;j>=0;j--)if(suff[j].compare(key)>0){suff[j+1]=suff[j];sa[j+1]=sa[j];}elsebreak;suff[j+1]=key;sa[j+1]=idx;}}};21第21页，共40页。后缀数组

的倍前缀算法voiddoubling(int*t){//构造后缀数组的倍前缀算法int*x=a,*y=b;for(inti=0;i<n;i++)x[i]=t[i],y[i]=i;radix(x,y,sa,n

,m);for(inth=1;h<n;h*=2){sort2(x,y,h);swap(x,y);x[sa[0]]=0;m=1;for(inti=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],h)

?m-1:m++;}}22第22页，共40页。voidradix(int*x,int*y,int*z,intn,intm){//根据y的序将x排序为zfor(inti=0;i<m;i++)cnt[i]=0;for(inti=0;i<n;i++)cnt[x[y[i]]

]++;//出现次数for(inti=1;i<m;i++)cnt[i]+=cnt[i-1];for(inti=n-1;i>=0;i--)z[--cnt[x[y[i]]]]=y[i];//排序}23第23页，共40页。voidsort2(int*x,int*y,inth){//

对2元序列对序列排序intt=0;for(inti=n-h;i<n;i++)y[t++]=i;for(inti=0;i<n;i++)if(sa[i]>=h)y[t++]=sa[i]-h;radix(x,y,sa,n,m);}24第24页

，共40页。后缀数组的DC3分治法voiddc3(int*t,int*sa,intn,intm){//构造后缀数组的DC3分治法int*t12=t+n,*sa12=sa+n,a0=(n+2)/3,a1=(n+1)/3,a12=a1

+n/3;t[n]=t[n+1]=0;intp=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;}25第25页，共40页。

intdivide(int*t,int*sa,int*t12,intn,intm,inta1,inta12){//非对称分割intd=0;for(inti=0;i<n;i++)if(i%3!=0)a[d++]=i;radix(t+2,a

,b,a12,m);radix(t+1,b,a,a12,m);radix(t,a,b,a12,m);d=1;t12[add1(b[0])]=0;for(inti=1;i<a12;i++)t12[add1(b[i])]=cmp(t,b[i-1],b[i])?d-1:d++;r

eturnd;}26第26页，共40页。voidconquer(int*t,int*sa12,int*t12,intn,intm,intp,inta1,inta12){//递归后缀排序inti,a0=0;if(p<a12)d

c3(t12,sa12,a12,p);elsefor(i=0;i<a12;i++)sa12[t12[i]]=i;for(i=0;i<a12;i++)if(sa12[i]<a1)b[a0++]=sa12[i]*3;if(n%3==1)b[a0++]=n-1;radix(t

,b,a,a0,m);}27第27页，共40页。voidmerge(int*t,int*sa,int*sa12,intn,intm,inta0,inta1,inta12){//后缀合并inti,j,p;for(i=0;i<a12;i++)b[i]=add2(sa12

[i]);for(i=0;i<a12;i++)c[b[i]]=i;for(i=0,j=0,p=0;i<a0&&j<a12;p++)sa[p]=cmp2(b[j]%3,t,a[i],b[j])?a[i++]:b[j++];for(;i<a0;p++)sa[p

]=a[i++];for(;j<a12;p++)sa[p]=b[j++];}28第28页，共40页。最长公共前缀与最长公共扩展算法voidkasai(int*t,int*sa,intn){//构造最长公共前缀数组lcpintk=0;sa[n]=n;for(inti=0

;i<n;i++)rank[sa[i]]=i;for(inti=0;i<n;i++){intj=sa[rank[i]+1];while(i+k<n&&j+k<n&&t[i+k]==t[j+k])k++;lcp[rank[i]]=k;if(k>0)k-

-;}}29第29页，共40页。intlce(intl,intr,intn){//最长公共扩展if(l==r)return(n-l);returnrmq(min(rank[l],rank[r]),max(ran

k[l],rank[r]));}30第30页，共40页。intrmq(intlow,inthigh){//区间最小查询intv=lcp[low];for(inti=low+1;i<high;

i++)if(lcp[i]<v)v=lcp[i];returnv;}31第31页，共40页。最长公共子串算法intlcss(strings1,strings2){//最长公共子串算法int*sa,*lcp,m,n,ans=0;

stringt;m=s1.length();n=s1.length()+s2.length();change(s1,s2,t);suffixsuf(t);sa=suf.sa;lcp=suf.lcp;for(inti=0;i<n-1;i++)if(lcp[i]>ans&&d

iff(sa,m,i))ans=lcp[i];returnans;}32第32页，共40页。voidchange(strings1,strings2,string&t){//字符串变换intm=s1.len

gth(),n=s2.length();t.resize(n+m+1);for(inti=0;i<m;i++)t[i]=s1[i];for(inti=0;i<n;i++)t[m+i+1]=s2[i];n=m+n+1;t[m]=t[n]=0;}33第

33页，共40页。编辑距离算法340,-1,(1,1)1,0-1,(1,1)1,-10,(,)(1,)1,min(,1)1,otherwise.(1,1)([],[]),ijdiijdjijdijdijdijdijx

iyj第34页，共40页。inted(){//编辑距离的动态规划算法for(inti=0;i<=n;i++

)d[i][0]=i;for(inti=0;i<=m;i++)d[0][i]=i;for(inti=0;i<n;i++)for(intj=0;j<m;j++)if(x[i]==y[j])d[i+1][j+1]=d

[i][j];elsed[i+1][j+1]=min(d[i][j]+dt,min(d[i][j+1],d[i+1][j])+1);returnd[n][m];}35第35页，共40页。voidback(inti,intj){//构造最

优编辑序列if(i==0||j==0)return;if(x[i-1]==y[j-1])back(i-1,j-1);elseif(d[i-1][j-1]+dt<min(d[i-1][j],d[i][j-1])+1){back(i-1,j-1);cout<<"r("

<<i-1<<","<<j-1<<")"<<endl;}elseif(d[i-1][j]<d[i][j-1]){back(i-1,j);cout<<"d("<<i-1<<")"<<endl;}else{back(i,j-1)

;cout<<"i("<<j-1<<")"<<endl;}}36第36页，共40页。intedn(){//O(n)空间算法memset(d1,0,sizeofd1);intoldd,newd;for(inti=0;i<=n;i++)for(i

ntj=0;j<=m;j++){if(i==0)oldd=d1[j],d1[j]=j;elseif(j==0)oldd=d1[j],d1[j]=i;else{if(x[i-1]==y[j-1])newd=oldd;elsenewd=min(oldd+dt,min(d1[j-1],

d1[j])+1);oldd=d1[j],d1[j]=newd;}}returnd1[m];}37第37页，共40页。最长公共单调子序列38(,)0,00(,)(1,),,0[][]1max(1,),,0ijtijijfijfijijx

iyjfitijxy第38页，共40页。intlcis(){//最长公共递增子序列memset(f,0,sizeof(f));for(inti=1;i<=n;i++){intmax=0;for(intj=1;j<=m;j+

+){f[i][j]=f[i-1][j];if(x[i-1]>y[j-1]&&max<f[i-1][j])max=f[i-1][j];if(x[i-1]==y[j-1])f[i][j]=max+1;}}intret=0;for(inti=1;i<=m;i++

)if(ret<f[n][i])ret=f[n][i];returnret;}39第39页，共40页。有约束最长公共子序列40(1,1,1)1,[][][](,,)(1,1,)1,[][]1max{(1,,),(,1,)},[][]fijkxiyjskfijkfijkxiyjkfij

kfijkxiyj第40页，共40页。