字符串匹配算法kmp递归实现

1. C语言如何实现KMP字符串匹配

#include <stdio.h>

#include <stdlib.h>

void KmpNextArray(const char* str, int len, int* next) {

/**/if (str == NULL || next == NULL || len <= 0) {

/**//**/return;

/**/}

/**/int n = 1;

/**/int i = 1;

/**/next[0] = 0;

/**/while (i < len && str[i] != str[0]) {

/**//**/next[i++] = 0;

/**/}

/**/if (i >= len) {

/**//**/return;

/**/}

/**/next[i++] = 1;

/**/for (; i < len; i++) {

/**//**/if (str[i] == str[n]) {

/**//**//**/next[i] = ++n;

/**//**/}

/**//**/else {

/**//**//**/next[i] = 0;

/**//**//**/n = 0;

/**//**/}

/**/}

}

int Strlen(const char* str) {

/**/if (str == NULL) {

/**//**/return 0;

/**/}

/**/int n = 0;

/**/while (str[n] != '') {

/**//**/++n;

/**/};

/**/return n;

}

const char* KmpFind(const char* str, const char* findstr) {

/**/if (NULL == str || NULL == findstr) {

/**//**/return NULL;

/**/}

/**/int slen = Strlen(str);

/**/if (0 == slen) {

/**//**/return NULL;

/**/}

/**/int flen = Strlen(findstr);

/**/if (0 == flen) {

/**//**/return NULL;

/**/}

/**/if (flen > slen) {

/**//**/return NULL;

/**/}

/**/int* next = (int*)malloc(sizeof(int) * flen);

/**/if (NULL == next) {

/**//**/return NULL;

/**/}

/**/KmpNextArray(findstr, flen, next);

/**/const char* p = str;

/**/int n = 0;

/**/while (p < str + slen) {

/**//**/if (findstr[n] == *p) {

/**//**//**/if (++n >= flen) {

/**//**//**//**/free((void*)next);

/**//**//**//**/return p - n + 1;

/**//**//**/}

/**//**//**/else {

/**//**//**//**/++p;

/**//**//**/}

/**//**/}

/**//**/else if (n > 0) {

/**//**//**/n = next[n - 1];

/**//**/}

/**//**/else {

/**//**//**/++p;

/**//**/}

/**/}

/**/free(next);

/**/return NULL;

}

int main(int argc, char* argv[]) {

/**/char a[100] = { 0 };

/**/char b[100] = { 0 };

/**/fgets(a, 100, stdin);

/**/fgets(b, 100, stdin);

/**///a b均带有换行符

/**/int alen = Strlen(a) - 1;

/**/int blen = Strlen(b) - 1;

/**/a[alen] = '';

/**/b[blen] = '';

/**/const char* p = KmpFind(a, b);

/**/if (NULL != p) {

/**//**/printf("%s %8d ", a, alen);

/**//**/for (int i = 0; i < (int)(p - a); i++) {

/**//**//**/putchar(' ');

/**//**/}

/**//**/printf("%0.*s %*d ", blen, p, 8 + alen - (int)(p - a) - blen, (int)(p - a));

/**/}

/**/else {

/**//**/printf("No string found! ");

/**/}

/**/return 0;

}

运行截图

2. kmp算法什么意思

KMP算法之所以叫做KMP算法是因为这个算法是由三个人共同提出来的，就取三个人名字的首字母作为该算法的名字。其实KMP算法与BF算法的区别就在于KMP算法巧妙的消除了指针i的回溯问题，只需确定下次匹配j的位置即可，使得问题的复杂度由O(mn)下降到O(m+n)。
在KMP算法中，为了确定在匹配不成功时，下次匹配时j的位置，引入了next[]数组，next[j]的值表示P[0...j-1]中最长后缀的长度等于相同字符序列的前缀。
对于next[]数组的定义如下：
1) next[j] = -1 j = 0
2) next[j] = max(k): 0<k<j P[0...k-1]=P[j-k,j-1]
3) next[j] = 0 其他
如：
P a b a b a
j 0 1 2 3 4
next -1 0 0 1 2
即next[j]=k>0时，表示P[0...k-1]=P[j-k,j-1]
因此KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。

3. 哭了~正在学数据结构中的 KMP 算法

KMP算法是拿来处理字符串匹配的。换句话说，给你两个字符串，你需要回答，B串是否是A串的子串（A串是否包含B串）。比如，字符串A="I'm matrix67"，字符串B="matrix"，我们就说B是A的子串。你可以委婉地问你的MM：“假如你要向你喜欢的人表白的话，我的名字是你的告白语中的子串吗？”
解决这类问题，通常我们的方法是枚举从A串的什么位置起开始与B匹配，然后验证是否匹配。假如A串长度为n，B串长度为m，那么这种方法的复杂度是O (mn)的。虽然很多时候复杂度达不到mn（验证时只看头一两个字母就发现不匹配了），但我们有许多“最坏情况”，比如，A= "aaaaaaaaaaaaaaaaaaaaaaaaaab"，B="aaaaaaaab"。我们将介绍的是一种最坏情况下O(n)的算法（这里假设 m<=n），即传说中的KMP算法。
之所以叫做KMP，是因为这个算法是由Knuth、Morris、Pratt三个提出来的，取了这三个人的名字的头一个字母。这时，或许你突然明白了AVL 树为什么叫AVL，或者Bellman-Ford为什么中间是一杠不是一个点。有时一个东西有七八个人研究过，那怎么命名呢？通常这个东西干脆就不用人名字命名了，免得发生争议，比如“3x+1问题”。扯远了。
个人认为KMP是最没有必要讲的东西，因为这个东西网上能找到很多资料。但网上的讲法基本上都涉及到“移动(shift)”、“Next函数”等概念，这非常容易产生误解（至少一年半前我看这些资料学习KMP时就没搞清楚）。在这里，我换一种方法来解释KMP算法。

假如，A="abababaababacb"，B="ababacb"，我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示，A[i-j+ 1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时，i和j各加一；什么时候j=m了，我们就说B是A的子串（B串已经整完了），并且可以根据这时的i值算出匹配的位置。当A[i+1]<>B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。我们看一看当 i=j=5时的情况。

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7

此时，A[6]<>B[6]。这表明，此时j不能等于5了，我们要把j改成比它小的值j'。j'可能是多少呢？仔细想一下，我们发现，j'必须要使得B[1..j]中的头j'个字母和末j'个字母完全相等（这样j变成了j'后才能继续保持i和j的性质）。这个j'当然要越大越好。在这里，B [1..5]="ababa"，头3个字母和末3个字母都是"aba"。而当新的j为3时，A[6]恰好和B[4]相等。于是，i变成了6，而j则变成了 4：

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7

从上面的这个例子，我们可以看到，新的j可以取多少与i无关，只与B串有关。我们完全可以预处理出这样一个数组P[j]，表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时，新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。
再后来，A[7]=B[5]，i和j又各增加1。这时，又出现了A[i+1]<>B[j+1]的情况：

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7

由于P[5]=3，因此新的j=3：

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7

这时，新的j=3仍然不能满足A[i+1]=B[j+1]，此时我们再次减小j值，将j再次更新为P[3]：

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7

现在，i还是7，j已经变成1了。而此时A[8]居然仍然不等于B[j+1]。这样，j必须减小到P[1]，即0：

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7

终于，A[8]=B[1]，i变为8，j为1。事实上，有可能j到了0仍然不能满足A[i+1]=B[j+1]（比如A[8]="d"时）。因此，准确的说法是，当j=0了时，我们增加i值但忽略j直到出现A[i]=B[1]为止。

最后的j:=P[j]是为了让程序继续做下去，因为我们有可能找到多处匹配。
这个程序或许比想象中的要简单，因为对于i值的不断增加，代码用的是for循环。因此，这个代码可以这样形象地理解：扫描字符串A，并更新可以匹配到B的什么位置。

现在，我们还遗留了两个重要的问题：一，为什么这个程序是线性的；二，如何快速预处理P数组。
为什么这个程序是O(n)的？其实，主要的争议在于，while循环使得执行次数出现了不确定因素。我们将用到时间复杂度的摊还分析中的主要策略，简单地说就是通过观察某一个变量或函数值的变化来对零散的、杂乱的、不规则的执行次数进行累计。KMP的时间复杂度分析可谓摊还分析的典型。我们从上述程序的j 值入手。每一次执行while循环都会使j减小（但不能减成负的），而另外的改变j值的地方只有第五行。每次执行了这一行，j都只能加1；因此，整个过程中j最多加了n个1。于是，j最多只有n次减小的机会（j值减小的次数当然不能超过n，因为j永远是非负整数）。这告诉我们，while循环总共最多执行了n次。按照摊还分析的说法，平摊到每次for循环中后，一次for循环的复杂度为O(1)。整个过程显然是O(n)的。这样的分析对于后面P数组预处理的过程同样有效，同样可以得到预处理过程的复杂度为O(m)。
预处理不需要按照P的定义写成O(m^2)甚至O(m^3)的。我们可以通过P[1],P[2],...,P[j-1]的值来获得P[j]的值。对于刚才的B="ababacb"，假如我们已经求出了P[1],P[2],P[3]和P[4]，看看我们应该怎么求出P[5]和P[6]。P[4]=2，那么P [5]显然等于P[4]+1，因为由P[4]可以知道，B[1,2]已经和B[3,4]相等了，现在又有B[3]=B[5]，所以P[5]可以由P[4] 后面加一个字符得到。P[6]也等于P[5]+1吗？显然不是，因为B[ P[5]+1 ]<>B[6]。那么，我们要考虑“退一步”了。我们考虑P[6]是否有可能由P[5]的情况所包含的子串得到，即是否P[6]=P[ P[5] ]+1。这里想不通的话可以仔细看一下：

1 2 3 4 5 6 7
B = a b a b a c b
P = 0 0 1 2 3 ?

P[5]=3是因为B[1..3]和B[3..5]都是"aba"；而P[3]=1则告诉我们，B[1]和B[5]都是"a"。既然P[6]不能由P [5]得到，或许可以由P[3]得到（如果B[2]恰好和B[6]相等的话，P[6]就等于P[3]+1了）。显然，P[6]也不能通过P[3]得到，因为B[2]<>B[6]。事实上，这样一直推到P[1]也不行，最后，我们得到，P[6]=0。

最后补充一点：由于KMP算法只预处理B串，因此这种算法很适合这样的问题：给定一个B串和一群不同的A串，问B是哪些A串的子串。

串匹配是一个很有研究价值的问题。事实上，我们还有后缀树，自动机等很多方法，这些算法都巧妙地运用了预处理，从而可以在线性的时间里解决字符串的匹配。

4. 数据结构 字符串 模式匹配问题 KMP算法

你的程序本身思路没有错，但错在以下几点：
1.在程序中有字符串S和T，你用S[0]代表字符串的长度，但S是字符串，S[0]是长度吗？
2.在main函数中，你输入的S和T都是用gets(S)或gets(T),那么它们都是以下标0开头的，你应该要进行处理，使它以下标1作为开头（可以这样gets(&S[1]); 然后S[0] = strlen(&S[1]) + '0';在用S[0]作为长度的时候，把它从字符变成数字就行了)。

5. 串的应用kmp算法。求一个字符串在另一个字符串中第一次出现的位置。

KMP.java

源代码为：

package algorithm.kmp;

/**
* KMP算法的Java实现例子与测试、分析
* @author 崔卫兵
* @date 2009-3-25
*/
public class KMP {
/**
* 对子串加以预处理，从而找到匹配失败时子串回退的位置
* 找到匹配失败时的最合适的回退位置，而不是回退到子串的第一个字符，即可提高查找的效率
* 因此为了找到这个合适的位置，先对子串预处理，从而得到一个回退位置的数组
* @param B，待查找子串的char数组
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循环一次，就会找到一个回退位置
for(int i=1;i<size;i++){
//当找到第一个匹配的字符时，即j>0时才会执行这个循环
//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
//p1
while(j>0 && B[j]!=B[i]){
j=P[j];
}
//p2，由此可以看出，只有当子串中含有重复字符时，回退的位置才会被优化
if(B[j]==B[i]){
j++;
}
//找到一个回退位置j，把其放入P[i]中
P[i]=j;
}
return P;
}

/**
* KMP实现
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int j=0;
int k =0;
for(int i=0;i<parSize;i++){
//当找到第一个匹配的字符时，即j>0时才会执行这个循环
//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
//p1
while(j>0 && B[j]!=A[i]){
//找到合适的回退位置
j=P[j-1];
}
//p2 找到一个匹配的字符
if(B[j]==A[i]){
j++;
}
//输出匹配结果，并且让比较继续下去
if(j==subSize){
j=P[j-1];
k++;
System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);
}
}
System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
}

public static void main(String[] args) {
//回退位置数组为P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!这个会匹配1次","abcdef");
//回退位置数组为P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!这个会匹配2次","ititit");
//回退位置数组为P[0, 0, 0]
kmp("测试汉字的匹配，崔卫兵。这个会匹配1次","崔卫兵");
//回退位置数组为P[0, 0, 0, 1, 2, 3, 4, 5, 6]
kmp("这个会匹配0次","it1it1it1");
}
}

6. 算法基础 - 朴素模式匹配算法、KMP模式匹配算法

假设我们要从 主字符串goodgoogle 中匹配 子字符串google
朴素模式匹配算法就是 通过从主字符的头部开始 一次循环匹配的字符串的挨个字符 如果不通过 则主字符串头部位置遍历位置+1 在依次遍历子字符串的字符

匹配过程
主字符串从第一位开始 取出g 子字符串取出第一位 g 匹配 进入子循环
取出o 取出o 匹配
取出o 取出o 匹配
取出d 取出g 不匹配 主字符串遍历位置+1

主字符串从第二位开始 取出o 子字符串取出第一位 g 不匹配 主字符串遍历位置+1

主字符串从第三位开始 取出o 子字符串取出第一位 g 不匹配 主字符串遍历位置+1

主字符串从第四位开始 取出d 子字符串取出第一位 g 不匹配 主字符串遍历位置+1

主字符串从第五位开始 取出g 子字符串取出第一位 g 匹配 进入子循环
取出o 取出o 匹配
取出o 取出o 匹配
取出g 取出g 匹配
取出l 取出l 匹配
取出e 取出e 匹配 子循环结束 匹配成功

假设主字符串 长度为 n 子字符串长度为m n>= m
最好的情况需要匹配m次 时间复杂度为 0(m)

例如 000000000001 匹配 00001 每次进入子循环之后 都要遍历到最后一次子循环才得出不匹配
需要匹配次数 (n-m+1) * m
最坏的情况需要匹配m次 时间复杂度为 0((n-m+1) * m)

KMP 算法的主要核心就是 子字符串在子循环内得出不匹配时 主字符串当前的判断位不需要回溯–也就是不可以变小 ，且子循环的判断位需要回溯 回溯位与子字符串本身是否具有重复结构有关 。 以此来规避无效的判断
时间复杂度为 O(n+m)

如果主串 S = "abcdefgab" 我们要匹配的子串 T = "abcdex" 如果用前面的朴素算法 ， 前5个字母完全相同
直到第6个字母 f 和 x 不同
步骤1
S: a b c d e f g a b
T: a b c d e x

接下来如果用朴素算法的话 那么应该是如下比较
步骤2
S: a b c d e f g a b
T: # a b c d e x
b 和 a 不匹配

步骤3
S: a b c d e f g a b
T: # # a b c d e x
a和c 不匹配

步骤4
S: a b c d e f g a b
T: # # # # a b c d e x
d和a 不匹配

步骤5
S: a b c d e f g a b
T: # # # # a b c d e x
a和e 不匹配

步骤6
S: a b c d e f g a b
T: # # # # # a b c d e x

即主串S中的第2 ，3 ， 4， 5， 6 位都与子串T的首字符不相等

对于子串T来说 如果首字符a与后面的bcdex中任意一个字符都不相等
那么对于上面的第一步来说 前五位都相等 那么 可以得到 子串首字符a 与主串的第2，3，4，5 位都不相等
即步骤2 ， 3 ，4 ，5 都是多余的 可以直接进入步骤6

如果子串的首字符串与后面的字符有相等的情况
假设S = "abcababca" T= "abcabx"

朴素算法
步骤1
S: a b c a b a b c a
T: a b c a b x
a 与 x 不匹配

步骤2
S: a b c a b a b c a
T: # a b c a b x
b 与 a 不匹配

步骤3
S: a b c a b a b c a
T: # # a b c a b x
c 与 a 不匹配

步骤4
S: a b c a b a b c a
T: # # # a b c a b x
a 与 a 匹配

步骤5
S: a b c a b a b c a
T: # # # # a b c a b x
b 与 b 匹配

步骤6
S: a b c a b a b c a
T: # # # # a b c a b x
a 与 c 不匹配

因为步骤1 中已经得出 前五位已经完全匹配 并且子串首字符ab 存在相同的情况 所以 步骤2，3 是多余的

直接进入步骤4 因为步骤1中已经得出 主串与子串前五位相同 同时 子串1 2 位与 子串的4 5 位相同 所以可得出
子串1 2 位 与当前主串匹配位置开始的前两位也就是主串的4 5 位匹配 所以步骤4 , 5 是多余的 可以直接进入步骤6

通过上面的两个例子我们可以发现 主串的比较位是不会回溯的 ， 而子串的比较位与子串本身结构中是否有重复相关

子串不重复 举例
S: a b c d e f g a
T: a b c d e x

子串第6位不匹配 且本身没有重复 那么下一次循环 就变成了 子串的第一位与主串的第二位比较
即子串的匹配位从6 变成了1

S: a b c d e f g a
T: # a b c d e x

子串重复 举例
S: a b c a b a b c a
T: a b c a b x
a 与 x 不匹配

子串在第六位发生不匹配是 前五位abcab 具有重复结构 ab 所以子串匹配位发生变化 即子串的匹配位从6 变成了 3

S: a b c a b a b c a
T: # # # a b c a b x
a 与 c 不匹配

我们可以得出 子串匹配位的值 与主串无关 只取决于当前字符串之前的串前后缀的相似度
也就是说 我们在查找字符前 ，要先对子串做一个分析 获取各个位置不匹配时 下一步子串的匹配位

前缀 ： 从头开始数 不包含最后一位
后缀 : 不是倒着数 是以和前缀相同的字符串为结尾的部分
例如 字符串 a 没有前后缀
字符串 ab 没有前后缀
字符串 aba 没有前后缀
字符串 abab 前后缀 ab
字符串 ababa 前后缀 可以是 a 可以是 aba 我们取长度最长的 即 aba

第一位时 next值固定为0
其他情况 取其公共最长前后缀的长度+1 没有则为1

因为一共子串有8位 所以在子循环内一共需要获取 8次前后缀
这里我们定义一个next数组 长度为8 里面的元素分别对应子串各个子循环内的 前后缀长度
第1位不匹配时 获取字符串为a 没有前字符串 没有前后缀 那么next[1] = 0
第2位不匹配时 获取字符串为ab 有前字符串a 没有前后缀 那么next[2] = 1
第3位不匹配时 获取字符串为aba 有前字符串ab 没有前后缀 那么next[3] = 1
第4位不匹配时 获取字符串为abab 有前字符串aba 前后缀 a 那么next[4] = 2
第5位不匹配时 获取字符串为ababa 有前字符串abab 前后缀 ab 那么next[5] = 3
第6位不匹配时 获取字符串为ababaa 有前字符串ababa 前后缀 aba 那么next[6] = 4
第7位不匹配时 获取字符串为ababaab 有前字符串ababaa 前后缀 a 那么next[7] = 2
第8位不匹配时 获取字符串为ababaabc 有前字符串ababaab 前后缀 ab 那么next[8] = 3

next数组为[ 0, 1 , 1 ,2 , 3, 4 ,2, 3 ]

后来有人发现 KMP还是有缺陷的 比如 当子串 T = "aaaaax"
在5位发生不匹配 此时 next[5] = 4 接着就是 子串中的第四位a与 主串当前位置字符比较

因为子串第五位等于子串第四位相同 所以可以得出该步骤也不匹配 此时 next[4] = 3
依然不匹配 直到next[1] = 0

我们可以发现由于T串中的 2 3 4 5 位置都与首位a 相等 中间的过程都是多余的
那么可以用首位的next[1] 的值 去替代与它相等的字符后续的next[x]的值

7. 判断两个字符串是否匹配，其中字符串中包括通配符*或(串)。*代表0个或多个字符代表一个字符

给你一个用递归算法写的字符串匹配函数，
非常精练，你可以参考一下，希望能看懂。
输入：
s，指向含通配符的匹配字符串，
d，指向要匹配的字符目标
返回值：
1，匹配一致
0，不能匹配

int StrMatch(const char *s,const char *d)
{ for(;*s;s++,d++)
{ if(*s=='*')
{ for(s++;;d++)
{ if(StrMatch(s,d))return 1;
if(*d==0)return 0;
}
}
if(*d==0)return 0;
if(*s!='?'&&*s!=*d)return 0;
}
return !(*d);
}

8. KMP算法详细代码

KMP.java

源代码为：

package algorithm.kmp;

/**
* KMP算法的Java实现例子与测试、分析
* @author 崔卫兵
* @date 2009-3-25
*/
public class KMP {
/**
* 对子串加以预处理，从而找到匹配失败时子串回退的位置
* 找到匹配失败时的最合适的回退位置，而不是回退到子串的第一个字符，即可提高查找的效率
* 因此为了找到这个合适的位置，先对子串预处理，从而得到一个回退位置的数组
* @param B，待查找子串的char数组
* @return
*/
public static int[] preProcess(char [] B) {
int size = B.length;
int[] P = new int[size];
P[0]=0;
int j=0;
//每循环一次，就会找到一个回退位置
for(int i=1;i<size;i++){
//当找到第一个匹配的字符时，即j>0时才会执行这个循环
//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
//p1
while(j>0 && B[j]!=B[i]){
j=P[j];
}
//p2，由此可以看出，只有当子串中含有重复字符时，回退的位置才会被优化
if(B[j]==B[i]){
j++;
}
//找到一个回退位置j，把其放入P[i]中
P[i]=j;
}
return P;
}

/**
* KMP实现
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int[] P = preProcess(B);
int j=0;
int k =0;
for(int i=0;i<parSize;i++){
//当找到第一个匹配的字符时，即j>0时才会执行这个循环
//或者说p2中的j++会在p1之前执行（限于第一次执行的条件下）
//p1
while(j>0 && B[j]!=A[i]){
//找到合适的回退位置
j=P[j-1];
}
//p2 找到一个匹配的字符
if(B[j]==A[i]){
j++;
}
//输出匹配结果，并且让比较继续下去
if(j==subSize){
j=P[j-1];
k++;
System.out.printf("Find subString '%s' at %d\n",subStr,i-subSize+1);
}
}
System.out.printf("Totally found %d times for '%s'.\n\n",k,subStr);
}

public static void main(String[] args) {
//回退位置数组为P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!这个会匹配1次","abcdef");
//回退位置数组为P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!这个会匹配2次","ititit");
//回退位置数组为P[0, 0, 0]
kmp("测试汉字的匹配，崔卫兵。这个会匹配1次","崔卫兵");
//回退位置数组为P[0, 0, 0, 1, 2, 3, 4, 5, 6]
kmp("这个会匹配0次","it1it1it1");
}
}

9. kmp 算法原理

朴素算法
先看看最“朴素”的算法： ///find a template in a string. #include<string.h> #include<stdio.h> int Index(char *S, char *T, int pos) { int k=pos, j=0; while(k <strlen(S) && j<strlen(T))//未超出字符串的长度 { if (S[k] == T[j]) { ++k; ++j;} //如果相同，则继续向后比较 else {k = k-j+1; j =0;} //如果不同，就回溯，重新查找 } if (j == strlen(T)) return k-strlen（T）; else return 0; }
编辑本段KMP算法
一种由Knuth(D.E.Knuth)、Morris(J.H.Morris)和Pratt(V.R.Pratt)三人设计的线性时间字符串匹配算法。这个算法不用计算变迁函数δ，匹配时间为Θ(n)，只用到辅助函数π[1，m]，它是在Θ(m)时间内，根据模式预先计算出来的。数组π使得我们可以按需要，“现场”有效的计算(在平摊意义上来说)变迁函数δ。粗略地说，对任意状态q=0，1，…，m和任意字符a∈Σ，π[q]的值包含了与a无关但在计算δ(q，a)时需要的信息。由于数组π只有m个元素，而δ有Θ(m∣Σ∣)个值，所以通过预先计算π而不是δ，使得时间减少了一个Σ因子。[1] KMP算法是通过分析子串，预先计算每个位置发生不匹配的时候，所需GOTO的下一个比较位置，整理出来一个next数组，然后在上面的算法中使用。
编辑本段KMP算法的讲解
当我们分析一个子串时，例如：abcabcddes. 需要分析一下，每个字符x前面最多有多少个连续的字符和字符串从初始位置开始的字符匹配。然后+1就行了（别忘了，我们的字符串都是从索引1开始的）当然，不要相同位置自己匹配，默认第一个字符的匹配数是0。
编辑本段定义
设字符串为 x1x2x3...xn ,其中x1，x2，x3，... xi，... xn均是字符，设ai为字符xi对应的整数。则a=m，当且仅当满足如下条件：字符串x1x2...xm equals 字符串x(i-m+1)...xi-1 xi 并且x1x2...xm x(m+1) unequals x(i-m) x(i-m+1)...xi-1 xi。
编辑本段举例
abcabcddes 0111234111 |----------------------默认是0 --| | |-----------------不能自己在相同位置进行字符匹配，所以这里认为没有匹配字符串，所以0+1 =1，继续从1开始匹配 ------| | |-----------前面的字符和开始位置的字符相同，所以是2,3,4 -----------| | | |-------不匹配只能取1。 希望能明白的是，如果开始字符是 Ch1的话，那么我们就是要在串中第2个Ch1后面的位置开始自己和自己匹配，计算最大的吻合度。 程序写出来就是： void GetNext(char* T, int *next) { int k=1,j=0; next[1]=0; while( k〈 T[0] ){ if (j ==0 || T[k] == T[j]) { ++k; ++j; next[k] = j; } else j= next[j]; } } 但是这个不是最优的，因为他没有考虑aaaaaaaaaaaaaaaaaaab的情况，这样前面会出现大量的1，这样的算法复杂度已经和最初的朴素算法没有区别了。所以稍微改动一下： void GetNextEx(char *T, char *next) { int k=1,j=0; next[1] = 0; while(k < T[0]) { if (j == 0 || T[k] == T[j]) { ++k; ++j; if (T[k] == T[j]) next[k] = next[j]; else next[k] = j; } else j = next[j]; } } 现在我们已经可以得到这个next字符串的值了，接下来就是KMP算法的本体了： 相当简单： int KMP(char* S, char* T, int pos) { int k=pos, j=1; while (k){ if (S[k] == T[j]){ ++k; ++j; } else j = next[j]; } if (j>T[0]) return k-T[0]; else return 0; } 和朴素算法相比，只是修改一句话而已，但是算法复杂度从O(m*n) 变成了：O(m)
编辑本段KMP算法的伪代码
KMP-MATCHER(T，P) 1n ← length[T] 2m ←length[P] 3π ← COMPUTE-PREFIX-FUNCTION(P) 4q ← 0△Number of characters matched. 5for i ← 1 to n△Scan the text from left to right. 6do while q>0 and P[q+1]≠T[i] 7do q ← π[q]△Next character does not match. 8if P[q+1]=T[i] 9then q ← q+1△Next character matches. 10if q=m△Is all of P matched? 11then print “Pattern occurs with shift” i-m 12q ← π[q]△Look for the next match. COMPUTE-PERFIX-FUNCTION(P) 1m ← length[P] 2π[1] ← 0 3k ← 0 4for q ← 2 to m 5do while k>0 and P[k+1]≠P[q] 6do k ← π[k] 7if P[k+1]=P[q] 8then k ← k+1 9π[q] ← k 10return π[1]
编辑本段KMP算法的c++实现
//c++实现的KMP算法，所有涉及字符串，其初始下标从0开始(上述算法均是从1开始) //example: char s[100],t[100];cin>>s>>t;KMP(s,t); //获取待查询模式的next数组 int* get_next(char* T, int* next){ int i = 0, j = -1; int length = strlen(T); int *temp = next; *next = -1; while(i< length){ if(j==-1 || *(T+i)==*(T+j)){ i++; j++; //优化后的get_next方法，可以防止出现形如"aaaaab"这种模式的计算退化 if(*(T+i)!=*(T+j)) *(next+i)=j; else *(next+i)=*(next+j); } else j=*(next+j); } return temp; } //KMP算法 int KMP(char *S, char *T){ int S_Length = strlen(S); int T_Length = strlen(T); //若模式长度大于字符串，则直接返回查询失败 if( S_Length < T_Length) return 0; int i = 0, j = 0; int* next = new int[T_Length]; get_next(T, next); while(i < S_Length && j < T_Length){ if(j == -1 || *(S+i) == *(T+j)){ i++; j++; } else j=*(next+j); } if(j>=T_Length) return i-T_Length; return 0; } 在此提供一个更简明的适用于字符串的kmp实现： #include<iostream> #include<string.h> int next[100]; void getnext(char b[]) { int i=1,j=0; //i是每个位子，j是回退的位子 next[1]=0; while(i<=strlen(b)) { if(j==0||b[i-1]==b[j-1]) { i++; j++; next[i]=j; } else j=next[j]; //用上一个的 回退关系 } } int kmp(char a[],char b[]) { int i=1,j=1; //i是主串中的位子 ，j匹配串的位子 while(i<=strlen(a)&&j<=strlen(b)) { if(j==0||a[i-1]==b[j-1]) { i++; j++; } else j=next[j]; } if(j>strlen(b)) return i-strlen(b); else return 0; } int main() { char a[40],b[40]; printf("要匹配的主串：\n"); scanf("%s",a); printf("要匹配的子串：\n"); scanf("%s",b); getnext(b); printf("输出next值：\n"); for(int i=1;i<=strlen(b);i++) printf("%d ",next[i]); printf("\n"); printf("%d",kmp(a,b)); system("pause"); main(); return 0; }
编辑本段串的最大匹配算法
摘要：
给定两个串S和T，长分别m和n，本文给出了一个找出二串间最大匹配的算法。该算法可用于比较两个串S和T的相似程度，它与串的模式匹配有别。
关键词：
模式匹配 串的最大匹配 算法 Algorithm on Maximal Matching of Strings Lin YuCai Xiang YongHong Zhang ChunXia Zhang JianJun （Computer Science Department of Yunnan Normal University Kunming 650092） ABSTRACT Given Two Strings S of length m and T of length n，the paper presents an algorithm which finds the maximal matching of them. The algorithm can be used to compare the similarility of the two strings S and T, it is different with the strings' pattren matching. KEY WORDS Pattern Matching Maximal Matching of Strings Algorithm
编辑本段问题的提出
字符串的模式匹配主要用于文本处理，例如文本编辑。文本数据的存储（文本压缩）和数据检索系统。所谓字符串的模式匹配[2]，就是给定两个字符串S和T，长度分别为m和n，找出T中出现的一个或多个或所有的S，在这方面已经取得了不少进展[3][4][5][6][7][8][9][10][11]。本文从文本处理的另一个角度出发，找出两个串的最大匹配，比较其相似程度[1]。它主要应用于文本比较，特别是在计算机辅助教学中。显然前者要找S的完全匹配，而后者并无此要求。例如，若S=ABCD，T=EFABCDX，那么模式匹配的结果就是找出了T中的一个ABCD，而我们算法的结果就是S能与T的ABCD完全匹配，但是T中还有3个字符是比S多出来的，也就是说在S中有100%的字符与T中的匹配，而在T中有57%的字符与S中的匹配。若S= ABCDFE，T=AFXBECDY。则在模式匹配中S与T无匹配项，但在我们的算法中就能发现T中存在A，B，C，D，但D后不存在E，F。而且S中也存在A，B，C，D，且具有顺序性。这样就能公正地评价S，T的区别。得知其相似程度。 文章的组织如下：首先介绍基本定义和问题的描述；第三节是算法设计；最后是本文总结。
编辑本段问题的描述
设∑为任意有限集，其元称为字符，w：∑→N为∑到N的函数，称为∑的权函数（注：本文仅讨论权值恒为1的情况）。∑*为∑上的有限字符串集合，那么对任意S，T∈∑*，设S=a1a2…am，T=b1b2…bn，m>0，n>0。记<m>={1,2, …,m},<n>={1,2, …,n}，则称{(i,j)∣i∈<m>，j∈<n>，ai=bj}为S与T的匹配关系集，记作M（S，T），称M为S与T的一个（容许）匹配，若对任意（i,j）, ( i',j' )∈，① i< i'，当且仅当j< j'，② i= i'当且仅当j= j'。S与T的匹配中满足 最大者，称为S与T的最大匹配。若C(i,j)为N上的m×n矩阵，且满足： 则称矩阵C为串S与T的匹配关系阵。 于是求串S与T的最大匹配，等价于求C中的一个最大独立点集M，它满足，若ci,j，ci',j'∈M，则i< i' 当且仅当j< j'，i=i'当且仅当j=j'。我们称这样的最大独立点集为C的最大C-独立点集。 例：设∑为所有字母的集合，对任意x∈∑，w（x）≡1，设S与T分别为：S=“BOOKNEWS”，T=“NEWBOOKS”。则我们可以得到S与T两个匹配： 这里=5； 这里 =4。 显然为串S与T的最大匹配。 S与T的匹配关系阵C可表示如下： 其中带圈的部分为一最大C-独立点集。
编辑本段算法设计
我们仅就权值为一的情况进行讨论。 设S和T为任意给定串，C为的S与T匹配关系阵，那么由2的讨论知，求S与T的最大匹配问题，等价于求C的最大C-独立点集问题。因而，为了解决我们的问题，只要给出求C的最大C-独立点集的算法就可以了。 显然，为了求出C的最大C-独立点集，我们可以采用这样的方法：搜索C的所有C-独立点集，并找出它的最大者。这种方法是可行的，但并不是非常有效的。这会使问题变得很繁，复杂度很大。因此，我们先对问题进行分析。 在下面的讨论中，我们把C的任一C-独立点集={ai1,j1，…，ais,js}，记作=ai1,j1…ais,js，i1 <…< is。于是可看作阵C中以1为节点的一条路，满足：对路中的任意两节点，均有某一节点位于另一节点的右下方。称这种路为右下行路。 于是求C-独立点集等价于求阵C的右下行路。这种求右下行路的搜索可以逐行往下进行。 命题1. 若 =αai,jβ和ψ=α'ai,jσ为C的两个C-独立点集，且α为α'的加细，则存在C-独立点集'=αai,jδ，满足≥。 命题2. 若 =αai,jβ和ψ=α'ai+k,jσ为C的两个C-独立点集，且≥，则存在C-独立点集'=αai,jδ，满足≥。 命题3. 若 =αai,jβ和ψ=α'ai,j+kσ为C的两个C-独立点集，且≥，则存在C-独立点集'=αai,jδ，满足≥。 由命题1知，在搜索右下行路的过程中，如果已获得了某一C-独立点集的某一初始截段αai,j和另一C-独立点集ψ的某一初始截段α'ai,j，且有≤，则我们可以停止对ψ的进一步搜索。 由命题2知，在搜索右下行路的过程中，在某一列j存在某两个C-独立点集的某初始截段=ai1,j1…ais,j和ψ=al1,m1…alt,j，如果≥，但lt>is，则我们可以停止对ψ的进一步搜索。 由命题3知，在搜索右下行路的过程中，在某一行i存在某两个C-独立点集的某初始截段=ai1,j1…ai,js和ψ=ai1,m1…ai,mt，如果≥，但mt>js，则我们可以停止对ψ的进一步搜索。 由此可见，并不要求搜索所有C的最大C-独立点集，而可以采用比这简单得多的方法进行计算。那么按照我们上面的三个命题，来看如下实例： 首先我们得到=B（在上的节点用①表示），我们向右下方找路，可以发现，在第4列有两个1，根据命题2，我们选择上面的一个1，也就是说选择第1行的那个1，而不要第2行的那个1。同时我们也发现在第1行也有两个1，由命题3知，我们选择左边的那个1，即第4列的那个1。此时=BO。但是当我们的算法运行到第4行时，=BOOK，由于K在第3行第6列，而本行的1在第1列，在路最后一个节点K的左边，那么我们必须新建一条路ψ，因为我们并不能确定是否以后就有≥，当算法运行到第6行时，=BOOK，ψ=NEW，=4，=3，我们将S链到路上，此时我们得到最长右下行路=BOOKS，=5。这样我们就可以计算出这两个字符串的匹配程度。 在我们的算法设计过程中，用到了两个技巧。技巧之一，矩阵C不用存储，是动态建立的，节省了空间。技巧之二，本算法并不要求所有的S与T中所有的元素都相互进行比较，也并不存储所有的右下行路，节省了时间和空间。由矩阵中1的出现情况可见，本算法所需的空间和时间都远小于O（mn）
编辑本段结束语
本文给出了一个与模式匹配不同的，具有若干应用的，串的最大匹配算法，该算法已经在机器上实现，达到了预期的效果。本文仅讨论权值恒为1的情况，对于权值任意的情形不难由此得到推广。
编辑本段C语言代码(C Code)
#include<stdio.h> #include<string.h> void getnext(int next[],char s[],int l) { int i=1,j=0; next[1]=0; while(i<l) { if(j==0 || s[i]==s[j]) { i++;j++; next[i]=j; } else j=next[j]; } } int KMP(char s1[],char s2[],int l1,int l2,int next[]) { int i,j; i=j=1; while(i<=l1 && j<=l2) { if(j==0||s1[i]==s2[j]) { i++;j++; } else j=next[j]; } if(j>l2) return(i-l2); return 0; } int main() { int next[10001],ans; char s1[10001],s2[10001],l1,l2; scanf("%s",s1+1); scanf("%s",s2+1); l1=strlen(s1+1); l2=strlen(s2+1); getnext(next,s2,l2); ans=KMP(s1,s2,l1,l2,next); if(ans!=0) printf("%d\n",ans); else printf("No!\n"); system("pause"); return 0; }
编辑本段KMP算法的pascal实现
var next:array [1 ..1000001] of longint; s,t:ansistring; procere get_next(t:ansistring); var j,k:integer; begin j:=1; k:=0; while j<length(t) do begin if (k=0) or (t[j]=t[k]) then begin inc(j); inc(k); next[j]:=k; end else k:=next[k]; end; end; function index(s:ansistring;t:ansistring):longint; var i,j:longint; begin get_next(t); index:=0; i:=1; j:=1; while (i<=length(s))and(j<=length(t)) do begin if (j=0)or(s[i]=t[j]) then begin inc(i); inc(j); end else j:=next[j]; if j>length(t) then index:=i-length(t); end; end; begin readln(s); readln(t); writeln(index(s,t)) end.
编辑本段KMP播放器
K-multimedia player的缩写
来自韩国的影音全能播放器，与Mplayer一样从linux平台移植而来的Kmplayer(简称KMP)几乎可以播放您系统上所有的影音文件。通过各种插件扩展KMP可以支持层出不穷的新格式。强大的插件功能,直接从Winamp继承的插件功能，能够直接使用winamp的音频 ，输入，视觉效果插件，而通过独有的扩展能力，只要你喜欢，可以选择使用不同解码器对各种格式进行解码。 KMPlayer The Professional Media Player! 它支持 Winamp 2/5 的输入、常规、DSP、视觉效果、媒体库插件。无须注册表支持直接调用 Directshow 滤镜！FFdshow 的视觉特效系统~超强的 GUI 界面~安装电视卡后可以直接代替原软件直接收看电视~支持播放 DVD/VCD 以及绝大多数电脑的媒体文件（AVI 支持 Xvid/DivX/3vid/H264 OGG/OGM/MKV 容器/AC3/DTS 解码~Monkey Audio 解码~）强烈推荐！此播放器除了会将自己的配置信息写入注册表外绝对绿色~ KMplayer内置目前常见的所有解码器，包括real,QT等。 另外KMplayer安装版也是目前很少见的检查流氓软件的安装方式，如果一旦有恶意的汉化小组汉化并捆绑了流氓软件。该安装程序自动会识别，并作出提示，建议用户不要安装，虽然不是特别准确，但KMplayer的无广告及第三方插件的特点使其深受好评。 目前韩国官方已经在Kmplayer里自带了中文字库，只要用户是中文系统，软件就会自动识别，十分方便。 KMP版本: KMPlayer3.0.0.1439

10. kmp算法的介绍

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。