kmp算法
说实话 ，看了大佬的讲解十分清晰，但是，，代码的实现部分还是表示不太理解他；
缺少实践；
不过这个博客讲的挺不错的 点击打开链接
d
讲道理其实还是不太懂 ，，，，
这东西，表示，难道说我脑回路不太正常，
关于KMP有个很重要的概念就是，next表的生成；
下面介绍《部分匹配表》是如何产生的。
首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
15.
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
－ "A"的前缀和后缀都为空集，共有元素的长度为0；
－ "AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；
－ "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
－ "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
－ "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；
－ "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；
－ "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。
16.
"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。
kmp算法是根据匹配表来减少循环匹配次数，而不再是最原始的，一位一位的去匹配和循环；
例如：
面，咱们就结合之前的《最大长度表》和上述结论，进行字符串的匹配。如果给定文本串“BBC ABCDAB ABCDABCDABDE”，和模式串“ABCDABD”，现在要拿模式串去跟文本串匹配，如下图所示：
1. 因为模式串中的字符A跟文本串中的字符B、B、C、空格一开始就不匹配，所以不必考虑结论，直接将模式串不断的右移一位即可，直到模式串中的字符A跟文本串的第5个字符A匹配成功： 2.继续往后匹配，当模式串最后一个字符D跟文本串匹配时失配，显而易见，模式串需要向右移动。但向右移动多少位呢？因为此时已经匹配的字符数为6个（ABCDAB），然后根据《最大长度表》可得失配字符D的上一位字符B对应的长度值为2，所以根据之前的结论，可知需要向右移动6 - 2 = 4 位。 3. 模式串向右移动4位后，发现C处再度失配，因为此时已经匹配了2个字符（AB），且上一位字符B对应的最大长度值为0，所以向右移动：2 - 0 =2 位。 4. A与空格失配，向右移动1 位。 5. 继续比较，发现D与C 失配，故向右移动的位数为：已匹配的字符数6减去上一位字符B对应的最大长度2，即向右移动6 - 2 = 4 位。 6. 经历第5步后，发现匹配成功，过程结束。
关于代码是如何而来
我的理解还不是很透彻，所以不加论述，搜索各个博客，大家说的挺好的1点击打开链接 2点击打开链接
这里直接上代码
上优化以后的代码
//优化过后的next 数组求法 void GetNextval(char* p, int next[]) { int pLen = strlen(p); next[0] = -1; int k = -1; int j = 0; while (j < pLen - 1) { //p[k]表示前缀，p[j]表示后缀 if (k == -1 || p[j] == p[k]) { ++j; ++k; //较之前next数组求法，改动在下面4行 if (p[j] != p[k]) next[j] = k; //之前只有这一行 else //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]] next[j] = next[k]; } else { k = next[k]; } } }对于直接进行匹配的，判断是否存在，并求第一个匹配位置
int KmpSearch(char* s, char* p) { int i = 0; int j = 0; int sLen = strlen(s); int pLen = strlen(p); while (i < sLen && j < pLen) { //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++ if (j == -1 || s[i] == p[j]) { i++; j++; } else { //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j] //next[j]即为j所对应的next值 j = next[j]; } } if (j == pLen) return i - j; else return -1; }
下面加一个
poj的kmp题目点击打开链接
#include <iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string> using namespace std; const int maxn=1000000+5; int next[maxn]; void getnext(string p) { int plen=p.size(); int k=-1; int j=0; next[0]=-1; while(j<=plen-1) { if(k==-1||p[j]==p[k]) { k++; j++; if(p[j]!=p[k]) next[j]=k; else next[j]=next[k]; } else k=next[k]; } } int kmp(string p,string s) { int plen=p.size(); int slen=s.size(); int j=0; int i=0; int ans=0; while(i<slen&&j<plen) { if(j==-1||s[i]==p[j]) { i++; j++; } else j=next[j]; if(j==plen) { ans++; j=next[j]; //cout<<i<<endl; } } return ans; } int main() { int n; cin>>n; string s,p; for(int i=0;i<n;i++) { memset(next,0,sizeof(next)); cin>>p>>s; getnext(p); // for(int i=0;i<p.size();i++) // cout<<next[i]<<endl; cout<<kmp(p,s)<<endl;; } // cout << "Hello world!" << endl; return 0; }
求一个串中，不重叠出现多少次
#include<iostream> #include<cstdio> #include<cstring> #include<string> using namespace std; char a[1005]; char b[1005]; int Next[1006]; int sum; void getNext() { int i=0,j=-1; Next[0]=j; int len=strlen(a); while(i<=len) { if(j==-1||a[j]==a[i]) { Next[++i]=++j; } else { j=Next[j]; } } /*for(int i0=0;i0<=len;i0++) { cout<<next[i0]<<" "; } cout<<endl;*/ } void kmp() { int lena=strlen(a); int lenb=strlen(b); int i=0,j=0; while(i<=lena&&j<=lenb) { if(j==-1||a[i]==b[j]) { i++;j++; } else { j=Next[j]; } if(j==lenb)//当完全匹配时j要求置零，即是重新开始找 { j=0; sum++; } } } int main() { while(~scanf("%s",a)&&a[0]!='#') { scanf("%s",b); getNext(); sum=0; kmp(); printf("%d\n",sum); } return 0; }