text: # Sunday匹配算法
  
  23 篇文章 0 订阅
  
  ## 总结：
  
  Sunday算法比BM算法还要快。
  
  ## 一：背景
  
  Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其效率在匹配随机的字符串时比其他匹配算法还要更快。Sunday算法的实现可比KMP，BM的实现容易太多。
  
  ## 二：分析
  
  A = “LESSONS TEARNED IN SOFTWARE TE”;
  B = “SOFTWARE”;
  Sunday算法的大致原理是：
  
  ## 三：完整代码
  
  #define _CRT_SECURE_NO_DEPRECATE
  
  #include<iostream>
  #include<string>
  
  using namespace std;
  
  int _next[256];
  string dest;
  string pattern;
  
  /*
  
  */
  void GetNext()
  {
  int len = pattern.size();//get the length
  
  for (int i = 0; i < 256; i++)
  _next[i] = -1;
  
  for (int i = 0; i < len; i++)
  _next[pattern[i]] = i;
  }
  
  int SundaySearch()
  {
  GetNext();
  
  int destLen = dest.size();
  int patternLen = pattern.size();
  
  if (destLen == 0) return -1;
  
  for (int i = 0; i <= destLen - patternLen;)
  {
  int j = i;//dest[j]
  int k = 0;//pattern[k]
  
  for (; k<patternLen&&j < destLen&&dest[j] == pattern[k]; j++, k++)
  ;//do nothing
  
  if (k == patternLen)//great! find it!
  return i;
  else
  {
  if (i + patternLen < destLen)
  i += (patternLen - _next[dest[i + patternLen]]);
  else
  return -1;
  }
  }
  
  return -1;
  }
  
  int main()
  {
  dest = "This is a wonderful city";
  
  //case one(successful locating)
  pattern = "wo";
  int result = SundaySearch();
  if (result == -1)
  cout << "sorry,you do not find it!\n";
  else
  cout << "you find it at " << result << endl;
  
  //case two(unsuccessful locating)
  pattern = "wwe";
  result = SundaySearch();
  if (result == -1)
  cout << "sorry,you do not find it!\n";
  else
  cout << "you find it at" << result << endl;
  
  return 0;
  }  
  
  • 1
  点赞
  • 2
  收藏
  觉得还不错? 一键收藏
  • 0
  评论
  10-17 2830
  06-27 213
  04-20 45
  12-07 510
  04-18
  10-16
  03-04
  09-05
  03-25
  
  ### “相关推荐”对你有帮助么？
  
  • 非常没帮助
  • 没帮助
  • 一般
  • 有帮助
  • 非常有帮助
  
  1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
  2.余额无法直接购买下载，可以购买VIP、C币套餐、付费专栏及课程。