時間匹配演算法

⑴ 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) 沒有太大意義