首页 / 算法 / Sunday算法模板

Sunday算法模板

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Sunday算法模板，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1852字，纯文字阅读大概需要3分钟。

内容图文

Sunday是一个线性字符串模式匹配算法。算法的概念如下：
Sunday算法是Daniel M.Sunday于1990年提出的一种字符串模式匹配算法。其核心思想是：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较，它在发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。
记模式串为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>
 4usingnamespace std;
 5int wei[301]={0};
 6int ans=0,lend,lenc,tot=0;//tot用于统计匹配次数，便于直观地与其他算法比较 7char c[10001],d[10001];
 8void pei()
 9{
10int w=0;//记录d匹配失败以后向右移动的数量 11while(w+lend<=lenc)
12    {
13int i=0;//正在匹配的位数 14bool f=false;//默次数认匹配成功 15while(i<=lend && f==false)
16        {
17if(c[i+w]!=d[i])
18             f=true;//匹配失败 19             i++;tot++;// 匹配下一位，匹配次数+1 20        }
21if(f==false)
22         {ans++;
23         cout<<i<<endl;
24         w++;}//当匹配成功的话就让b串整体右移一位，与a串的下一位进行匹配 25else//匹配失败 26        {
27             i=lend+1;// 直接匹配a串中b串再次出现的位置 28if(wei[c[i+w]]==-1)
29             w=w+i+1;//没有出现过得话，就让b串整体右移lend+1位 30else w=w+i-wei[c[w+i]];//如果出现过的话就跳到出现位置？ 31        }
32    }
33return;
34}
35int main()
36{
37    gets(c);
38    gets(d);
39     lenc=strlen(c)-1;
40     lend=strlen(d)-1;
41for(int i=0;i<=300;++i)wei[i]=-1;
42for(int i=0;i<=lend;++i)
43     wei[d[i]]=i;//记录每一个字符出现的位置 44    pei();
45if(ans)
46     cout<<ans<<endl<<tot;
47else cout<<"mission failed";
48return0;
49 }

 

原文：http://www.cnblogs.com/zwfymqz/p/6788749.html

内容总结

以上是互联网集市为您收集整理的Sunday算法模板全部内容，希望文章能够帮你解决Sunday算法模板所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1168127.html

来源：【匿名】