用kmp算法实现字符串匹配

⑴ 题目：KMP算法的实现 内容： 实现字符串匹配的简单匹配算法和KMP算法，并且使用相同的比较字符串重复比较

shit

⑵ kmp算法的介绍

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

⑶ 数据结构 字符串 模式匹配问题 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]作为长度的时候，把它从字符变成数字就行了)。

⑷ kmp算法的RK串匹配

programRK;begin{计算x,x:=d↑（m-1）modq}x=1fori=1tom-1dox=（32*x)modq{计算模式W的散列函数值}s=0fori=1tomdos=((s*32）+ord(w[i]))modq{计算正文T的第一个长度为m的字符段的散列函数值}t=0fori=1tomdot=(t*32+ord(w[i]))modq{如果正文的第一个长度为m的字符段和模式有相同的散列函数值，则进行匹配检查.否则，以及在匹配检查失败情况下，继续计算下一个字符段的散列函数值}i=1whilei<=n-mdoifs=t{进行匹配检查}k=1j=iwhile(t[j]=w[k])and(k<=m)doj=j+1k=k+1endwhileifi<n-m{计算下一字符段的散列函数值}t=((t-x*ord(t[i]))*32+ord(t[i+m]))modqi=i+1endifendifendwhilereturn“FAILURE”end显然，如果不计执行匹配检查的时间，则RK算法的剩余部分执行时间是Θ（m+n)。不过，如果计及执行匹配检查的时间，则在理论上，RK算法需要时耗Θ（mn）。但是，我们总可设法取q适当大，使得mod函数在计算机中仍可执行而冲突（即不同的字符串具有相同的散列值）又极小可能发生，而使算法的实际执行时间只需Θ（m+n）。
BM算法
BM算法和KMP算法的差别是对模式串的扫描方式自左至右变成自右至左。另一个差别是考虑正文中可能出现的字符在模式中的位置。这样做的好处是当正文中出现模式中没有的字符时就可以将模式大幅度滑过正文。
BM算法的关键是根据给定的模式W[1,m]，，定义一个函数d: x->{1,2，…，m},这里x∈∑。函数d给出了正文中可能出现的字符在模式中的位置。

⑸ kmp算法详解

KMP模式匹配算法
KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的明[4]。
求得模式的特征向量之后，基于特征分析的快速模式匹配算法(KMP模式匹配算法)与朴素匹配算法类似，只是在每次匹配过程中发生某次失配时，不再单纯地把模式后移一位，而是根据当前字符的特征数来决定模式右移的位数[3]。
include "string. h"

#include<assert. h>

int KMPStrMatching(String T, String P, int. N, int startIndex)

{int lastIndex=T.strlen() -P.strlen();

if((1 astIndex- startIndex)<0)//若 startIndex过大,则无法匹配成功

return (-1);//指向P内部字符的游标

int i;//指向T内部字符的游标

int j=0;//指向P内部字符的游标

for(i= startIndex; i <T.strlen(); i++)

{while(P[j]!=T[i]&& j>0)

j=N[j-1];

if(P[j]==T[i])

j++;

if(j ==P.strlen())

return(1-j+1);//匹配成功,返回该T子串的开始位置

}

return (-1);

}

⑹ 算法基础 - 朴素模式匹配算法、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]的值

⑺ Java编程实现字符串的模式匹配

传统的字符串模式匹配算法（也就是BF算法）就是对于主串和模式串双双自左向右，一个一个字符比较，如果不匹配，主串和模式串的位置指针都要回溯。这样的算法时间复杂度为O（n＊m），其中n和m分别为串s和串t的长度。

KMP 算法是由Knuth，Morris和Pratt等人共同提出的，所以成为Knuth－Morris－Pratt算法，简称KMP算法。KMP算法是字符串模式匹配中的经典算法。和BF算法相比，KMP算法的不同点是匹配过程中，主串的位置指针不会回溯，这样的结果使得算法时间复杂度只为O（n＋m）。

⑻ 求出子串（模式串）的next函数值，利用kmp算法实现模式与主串的匹配算法

有两种算法：(len为模式串长度,T[]为模式串)
1、i = 1; j = 0; next[1] = 0;
while(i<len)
{
if((j == 0)||(T[i] == T[j]))
{
i++; j++;
next[i] = j;
}
else
j = next[i];
}

2、i = 1; j = 0; next[1] = 0;
while(i<len)
{
if((j == 0)||(T[i] == T[j]))
{
i++; j++;
if(T[i] != T[j])
next[i] = j;
else
next[i] = next[j];
}
else
j = next[i];
}
总的来说第二种方法相对于第一种方法有改进，因为第一种方法在一些情况下有缺陷，如模式串为"aaaab"时。自己好好体会吧

⑼ 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;

}

运行截图