- //kmp.h : kmp算法。
- //*************************************************************************
- //Remarks:
- //kmp解决了模式串指针回溯的问题,通过对模式串进行预处理(寻找最长前缀),
- //先将回溯的距离计算好,从而使算法复杂度从朴素的O(mn)降低到O(m+n)
- //
- //*************************************************************************
- #ifndef _my_kmp_
- #define _my_kmp_
- #include <string.h>
- #include <vector>
- using std::vector;
- //res 用来存放匹配的位移
- inline void kmp(const char * ori, const char * pat, vector<int> * res)
- {
- int olen=strlen(ori);
- int plen=strlen(pat);
- int * next=new int[plen];
- next[0]=0;
- for (int i=1,j=0;i<plen;++i)
- {
- j=next[i-1];
- while (j>0&&pat[j]!=pat[i])
- {
- j=next[j-1];
- }
- if (pat[j]==pat[i])
- {
- ++j;
- }
- next[i]=j;
- }
- for (int i=0,j=0;i<olen;++i)
- {
- while (j>0&&ori[i]!=pat[j])
- {
- j=next[j-1];
- }
- if (ori[i]==pat[j])
- {
- ++j;
- }
- if (j==plen)
- {
- (* res).push_back(i-j+1);
- }
- }
- delete []next;
- }
- #endif
- //该片段来自于http://www.codesnippet.cn/detail/130820135114.html
来源: http://www.codesnippet.cn/detail/130820135114.html