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

}

運行截圖