- //Sunday.h : Sunday算法。
- //Remarks: Sunday算法是比较快速的字符串匹配算法,比KMP和Booyer-moore算法都
- //快,这三种算法都需要提前进行预处理,Booyer-moore是反向比对字符串,Kmp和
- //Sunday则是正向比对,各自的预处理方法都不同。
- //Sunday算法主要思想是让指向主串的指针在匹配过程中,跳过尽可能多的长度,
- //再和模式串进行匹配。平均状况下时间复杂度:O(主串长度/模式串长度)。
- //*************************************************************************
- #ifndef _my_sunday
- #define _my_sunday
- #include <string.h>
- #include <vector>
- using std::vector;
- inline void sunday(const char* ori ,const char* pat, vector<int> * res)
- {
- int i=0;
- int j=0;
- int olen=strlen(ori);
- int plen=strlen(pat);
- const int max_size=255;
- int * next =new int[max_size];
- for (i=0;i<max_size;++i)
- {
- next[i]=plen+1;
- }
- for (i=0;i<plen;++i)
- {
- next[pat[i]]=plen-i;
- }
- i=0;
- while(i<=olen-plen)
- {
- while(j<plen)
- {
- if (ori[i+j]!=pat[j])
- {
- break;
- }
- ++j;
- }
- if (j==plen)
- {
- (*res).push_back(i);
- j=0;
- }
- i+=next[ori[i+plen]];
- }
- }
- #endif
- //该片段来自于http://www.codesnippet.cn/detail/140820135153.html
来源: http://www.codesnippet.cn/detail/140820135153.html