Sunday算法模板新普京娱乐场

Sunday是叁个线性字符串方式相称算法。算法的概念如下:

Sunday算法是丹尼尔勒M.Sunday于一九八九年提出的生龙活虎种字符串方式相配算法。其核激情想是:在特别进程中,方式串并不被供给一定要按从左向右进行比较依旧从右向左实行相比较,它在开掘不匹配时,算法能跳过玩命多的字符以实行下一步的匹配,进而压实了合作功用。

记形式串为S,子串为T,长度分别为N,M。

对于T,大家做二个粗略而玄妙的预管理:记录T中每意气风发种字符最终现身的职位,将其存入三个数组中。

如果在发生不相配时S[i]≠T[j],1≤i≤N,1≤j≤M。设S本次率先个门户差不多的字符地点为L。显著,S[L+M+1]断定要参与下意气风发轮的特别,何况T最少要与S[L+M+1]万分才有十分的大大概与一切S相称。

那个时候大家就招来T中S[L+M+1]并发之处了。利用大家预管理好的数组,能够O(1)查寻觅拾壹分地方u,并将其直接移动至T[u]==S[L+M+1]。特殊地,若S[L+M+1]不曾在T中冒出,那么T不恐怕会与S[L+M+1]十三分,则将T的第一人间接移动到S[L+M+2],继续合营。直至L+M>N时,相称完毕。

Sunday算法观念跟BM算法很寻常,在极其战败时关怀的是文本串中参与相称的最倒数一位字符的下一个人字符。假诺该字符未有在相称串中出现则间接跳过,即活动步长=
相配串长度+1;不然,同BM算法同样其运动步长=相配串中最右端的该字符到末尾的间隔+1。

算法举个例子

S:abcceabcaabcd

T:abcd

发现d与c不匹配。此时S[L+M+1]==’e’,未有出以后T中。于是:

S:abcceabcaabcd

T:——–abcd

发现d与a不匹配。此时S[L+M+1]==’a’,T中最后出将来T[0]。于是:

S:abcceabcaabcd

T:————–abcd

水到渠成般配。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 int wei[301]={0};
 6 int ans=0,lend,lenc,tot=0;//tot用于统计匹配次数,便于直观地与其他算法比较
 7 char c[10001],d[10001];
 8 void pei()
 9 {
10     int w=0;//记录d匹配失败以后向右移动的数量 
11     while(w+lend<=lenc)
12     {
13         int i=0;//正在匹配的位数 
14         bool f=false;//默次数认匹配成功 
15         while(i<=lend && f==false)
16         {
17             if(c[i+w]!=d[i])
18             f=true;//匹配失败 
19             i++;tot++;// 匹配下一位,匹配次数+1 
20         }
21         if(f==false)
22         {ans++;
23         cout<<i<<endl;
24         w++;}//当匹配成功的话就让b串整体右移一位,与a串的下一位进行匹配 
25         else//匹配失败 
26         {
27             i=lend+1;// 直接匹配a串中b串再次出现的位置 
28             if(wei[c[i+w]]==-1)
29             w=w+i+1;//没有出现过得话,就让b串整体右移lend+1位 
30             else w=w+i-wei[c[w+i]];//如果出现过的话就跳到出现位置? 
31         }
32     }
33     return;
34 }
35 int main()
36 {
37     gets(c);
38     gets(d);
39     lenc=strlen(c)-1;
40     lend=strlen(d)-1;
41     for(int i=0;i<=300;++i)wei[i]=-1;
42     for(int i=0;i<=lend;++i)
43     wei[d[i]]=i;//记录每一个字符出现的位置 
44     pei();
45     if(ans)
46     cout<<ans<<endl<<tot;
47     else cout<<"mission failed";
48     return 0;
49 }

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图