时间匹配算法

⑴ 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∣Σ∣）个值，所以通过预先计算π而不是δ，使得时间减少了一个Σ因子。

⑵ 我的KMP算法做出来了，可是居然运行时间比普通匹配还慢求高手解答，帮忙修改一下！

①你的KMP代码里很多东西导致KMP算法变慢：
1、计算主字符串长度很浪费时间，可以不用计算的，事先开辟一个大空间。
2、new int[len+1];很浪费时间，事先开辟大空间，或者用多级内存管理。
3、delete []next很浪费时间。

②但是①说的不是本质，真正的原因是：KMP的优点是避免重复匹配的记忆功能，缺点是启动慢构造next，这就导致如果要被匹配的主字符串太短（少于1k个字符都算短的）。
而朴素算法启动不需要时间。

③另一方面，你的main中主字符串和匹配字符串没有相似性（只在最后2个字符串才进行了一次大的返回），而KMP的优点就在于处理相似字符串匹配，相似度越高，字符串越长，匹配效果越好。

④我改了下你的代码，增加的主字符串的长度，提高了字符串相似程度，结果就是KMP的时间比朴素算法要好接近30%：
Time to do Index loops is 32.031
Time to do KMP loops is 23.609

⑤代码如下：

#include<time.h>
#include <iostream.h>
#include <string.h>
int Index_BF ( char S [ ], char T [ ], int pos )
{
int i = pos, j = 0;
while ( S[i+j] != '\0'&& T[j] != '\0')
if ( S[i+j] == T[j] )
j ++;
else
{
i ++; j = 0; }
if ( T[j] == '\0')
return i;
else
return -1;
}
void get_nextval(const char *T, int next[])
{
int j = 0, k = -1;
next[0] = -1;
while ( T[j/*+1*/] != '\0' )
{
if (k == -1 || T[j] == T[k])
{
++j; ++k;
if (T[j]!=T[k])
next[j] = k;
else
next[j] = next[k];
}// if
else
k = next[k];
}

}

int KMP(const char *Text,const char* Pattern) //const 表示函数内部不会改变这个参数的值。
{
if( !Text||!Pattern|| Pattern[0]=='\0' || Text[0]=='\0' )//
return -1;//空指针或空串，返回-1。

static int next[50];
get_nextval(Pattern,next);//求Pattern的next函数值

static int index,i,j;
index=i=j=0;
for(;Text[i]!='\0' && Pattern[j]!='\0';)
{
if(Text[i]== Pattern[j])
{
++i;// 继续比较后继字符
++j;
}
else
{
index += j-next[j];
if(next[j]!=-1)
j=next[j];// 模式串向右移动
else
{
j=0;
++i;
}
}
}

//delete []next;
if(Pattern[j]=='\0')
return index;// 匹配成功
else
return -1;
}

int main()//abCabCad
{
int i;

char* text= "jirjhirjgijerigjir\
rgr\
jirjhirjgijerigjir\
rgr\
jirjhirjgijerigjir\
dCadtttccadCadCadtttcc\
dtttccadCadCadtttcc\
\
jgirejgijreijgirejgijreijgirejgijreijgirejgijreijgirejgijreijgirejgijreijgirejgijreijgirejgijreigfgergregegrgergegirjgirjgirjigjierjgijjgirejgijreijgirejgijreirighrjigjeigjadCadCadjreigjrijgirejgijreigfgergrege\
adCadCadtttccctctc";

char*pattern="adCadCadtttccctctc";

clock_t start, finish;
double ration;
//普通匹配算法
cout<<( "Time to do Index loops is ") ;
start = clock();
for(int k=0;k<50000;k++)
{
i=Index_BF(text,pattern,1);

}
finish = clock();
ration = (double)(finish - start) / CLOCKS_PER_SEC;
cout<<( "%f seconds\n", ration )<<endl;
//KMP匹配算法
cout<<( "Time to do KMP loops is ")<<endl;
start = clock();
for(int j=0;j<50000;j++)
{
i=KMP(text,pattern);
}
finish = clock();
ration = (double)(finish - start) / CLOCKS_PER_SEC;
cout<<( "%f seconds\n", ration )<<endl;

cin>>finish;
return 0;

}

⑶ 字符串匹配算法，最快的是哪种

目前在我遇到的字符串匹配算法中，最快的应该是sunday算法了。。
(BF、KMP、BM、sunday)

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

⑸ KMP算法不是很理解 C++

KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度为O(m+n).。
一． 简单匹配算法
先来看一个简单匹配算法的函数：
int Index_BF ( char S [ ], char T [ ], int pos )
{
/* 若串 S 中从第pos(S 的下标0≤pos<StrLength(S))个字符
起存在和串 T 相同的子串，则称匹配成功，返回第一个
这样的子串在串 S 中的下标，否则返回 -1 */
int i = pos, j = 0;
while ( S[i+j] != '\0'&& T[j] != '\0')
if ( S[i+j] == T[j] )
j ++; // 继续比较后一字符
else
{
i ++; j = 0; // 重新开始新的一轮匹配
}
if ( T[j] == '\0')
return i; // 匹配成功 返回下标
else
return -1; // 串S中(第pos个字符起)不存在和串T相同的子串
} // Index_BF

此算法的思想是直截了当的：将主串S中某个位置i起始的子串和模式串T相比较。即从 j=0 起比较 S[i+j] 与 T[j]，若相等，则在主串 S 中存在以 i 为起始位置匹配成功的可能性，继续往后比较( j逐步增1 )，直至与T串中最后一个字符相等为止，否则改从S串的下一个字符起重新开始进行下一轮的"匹配"，即将串T向后滑动一位，即 i 增1，而 j 退回至0，重新开始新一轮的匹配。

⑹ KMP模式匹配算法是什么

KMP模式匹配算法是一种改进算法，是由D.E.Knuth、J.H.Morris和v.R.Pratt提出来的，因此人们称它为“克努特－莫里斯－普拉特操作”，简称KMP算法。此算法可以在O（n＋m）的时间数量级上完成串的模式匹配操作。其改进在于：每当一趟匹配过程出现字符不相等时，主串指针i不用回溯，而是利用已经得到的“部分匹配”结果，将模式串的指针j向右“滑动”尽可能远的一段距离后，继续进行比较。

1.KMP模式匹配算法分析回顾图4－5所示的匹配过程示例，在第三趟匹配中，当i＝7、j＝5字符比较不等时，又从i＝4、j＝1重新开始比较。然而，经仔细观察发现，i＝4和j＝1、i＝5和j＝1以及i＝6和j＝1这三次比较都是不必进行的。因为从第三趟部分匹配的结果就可得出，主串中的第4、5和6个字符必然是b、c和a（即模式串第2、第2和第4个字符）。因为模式中的第一个字符是a，因此它无须再和这三个字符进行比较，而仅需将模式向右滑动2个字符的位置进行i＝7、j＝2时的字符比较即可。同理，在第一趟匹配中出现字符不等时，仅需将模式串向右移动两个字符的位置继续进行i＝2、j＝1时的字符比较。由此，在整个匹配过程中，i指针没有回溯，如图1所示。

图1改进算法的模式匹配过程示意

⑺ 目前时间复杂度最好的字符串匹配算法是什么

KMP是O(n+m)，你可以上网搜索一下。
还有扩展KMP,是针对不同的问题。
以及Trie等多模式匹配。
总之都能方便搜索到啦。

⑻ 串的模式匹配算法中的BRUTE FORCE算法在最好情况下的时间复杂度为什么是O(n+m)而不是O(m)其中m是模式...

理解你的意思,你觉得O(m)是第一次搜索就找到推出函数了对吧, 这时候你可以认为是O(m), 但是 当 文本中找不到模式串的时候,比如 bbbbb中找a ,是不需要扫描一下文本bbbbb, 复杂度就是O(n), 说成O(n+m) 没有太大意义