公司网站建设开发维护工作,免费微网站,世界500强设计公司有哪些,做网站的语言版本背景Sunday 算法是 Daniel M.Sunday 于 1990 年提出的字符串模式匹配。其效率在匹配随机的字符串时比其他匹配算法还要更快。Sunday 算法的实现可比 KMP#xff0c;BM 的实现容易太多。算法过程假定主串为 HERE IS A SIMPLE EXAMPLE#xff0c;模式串为 EX… 背景Sunday 算法是 Daniel M.Sunday 于 1990 年提出的字符串模式匹配。其效率在匹配随机的字符串时比其他匹配算法还要更快。Sunday 算法的实现可比 KMPBM 的实现容易太多。算法过程假定主串为 HERE IS A SIMPLE EXAMPLE模式串为 EXAMPLE。1从头部开始比较发现不匹配。则 Sunday 算法要求如下找到主串中位于模式串后面的第一个字符即红色箭头所指的 “空格”再在模式串中从后往前找“空格”没有找到则直接把模式串移到“空格” 的后面。23找到匹配。完整代码/**** author : 刘毅Limer* date : 2017-07-30* mode : C*/ #include iostream#include string #define MAX_CHAR 256#define MAX_LENGTH 1000 using namespace std; void GetNext(string p, int m, int next[]){ for (int i 0; i MAX_CHAR; i) next[i] -1; for (int i 0; i m; i) next[p[i]] i;} void Sunday(string s, int n, string p, int m){ int next[MAX_CHAR]; GetNext(p, m, next); int j; // s 的下标 int k; // p 的下标 int i 0; while (i n - m) { j i; k 0; while (j n k m s[j] p[k]) j, k; if (k m) cout 在 i 处找到匹配\n; if (i m n) i (m - next[s[i m]]); else return; } // PS: 匹配失败不作处理} int main(){ string s, p; int n, m; while (cin s p) { n s.size(); m p.size(); Sunday(s, n, p, m); cout endl; } return 0;}数据测试如下图来源https://www.61mon.com/index.php/archives/213/
