關於KMP演算法，哪位大師可以幫助實現它

我已為您將其更改為 C。

驗證演算法並顯示第乙個位置。

如下：包括

#include

int getsubstr(char * str,char * substr)

int i,j;

bool flag;

for(i=0 ; iflag=true;

for(j=0; jif(str[i+j]!=substr[j])

flag=false;

break;

if(flag)

return i;

return -1;

int main()

int getsubstr(char * str,char * substr) ;

char a[ 20] ;

char b[ 20 ]

printf("請輸入源字串：" )

scanf("%s",&a) ;

printf("請輸入您要查詢的字串：") ;

scanf("%s", &b )

int j =getsubstr(a,b) ;

if( j != -1 )

printf("子字串位置從源字串的 %d 位開始。 ", j+1 );

else printf("未找到匹配的子字串") ;

return 0;

（1）未改進的模式匹配演算法的時間複雜度為o（n m），但總體上其實際執行時間接近o（n m），因此至今仍在使用。

2）只有當模式和主字串之間存在許多“部分”匹配時，KMP演算法才會比未改進的模式匹配出現得更快。

2）KMP演算法最大的特點是指示主字串的指標不需要回溯，在整個匹配過程中只需要從頭到尾掃瞄主字串，這對於處理儲存在外部儲存器中的大檔案非常有效。

要匹配的字串以許多重複的字串為字首，目標字串也包含很多，例如在“abababababababc”中找到“abababc”

KMP 演算法的時間複雜度為 o（n+m），其中 n 是原始字串的長度，m 是字串的長度。

KMP演算法的核心是NEXT陣列，當某個位置不匹配時，它可以快速找到與子字串字首相同的第乙個位置，並繼續匹配，無需重複不必要的操作，大大降低了時間複雜度。

我們不提下乙個陣列是如何生成的，但讓我們解釋一下如何使用下乙個陣列。

例如，如果 abababac 與 ababac 匹配，則假定父字串的下標為 i，子字串下標為 j，字串前導下標為 1

首先，兩個字串對齊。

abababac

ababac

當匹配到達第六個位置時，發現不匹配。

傳統演算法將 i 移動到第二位，j 移動到第一位，並繼續匹配。

即：abababac

ababac

另一方面，KMP 演算法將直接固定 J=Next[J]，i 的位置。

在這種情況下，next[6]=4，即將 j 移動到第四個位置。

即：abababac

ababac

此時，比賽將繼續成功。 由於 i 不向前移動，因此時間複雜度為 o（n+m）。

KMP 匹配 C++**：

int next[100];

char str1[100],str2[100];

void kmp_cmp()

對於下乙個陣列。

也就是說，子字串的最後乙個位置及其自己的通用字首。

這可能有點抽象，但說白了，它是子字串與自身匹配的最長公共字首，該位置為最後一位。

在計算下乙個陣列的第 i 個位置時，該位置的所有先前的 next 值都已經計算完畢，因此我們可以借助 next[i] 的前乙個值來更新 next[i] 的值。

所以時間複雜度是 o（2*m）。

以 ababac 為例：

第 1 步：ababac

ababac

i，j 在開始時不匹配，即 next[2]=0。

第 2 步：阿巴巴

ababac

i，j 匹配位置 3，next[3]=1

類似：next[4]=2， next[5]=3， next[6]=4

在 i=6、j=4 處存在不匹配。

因此，j=next[j]+1，i++，即匹配的字串向後移動。

即：ababac

_ababac

在這種情況下，兩個字串不匹配，next[7]=0

查詢下乙個陣列 **：

int next[100];

char str2[100];

void get_next()

elsej=next[j];

以上就是下面對KMP演算法的理解，如果有什麼不足之處請見諒，如果有什麼不明白的地方，也請提出問題。

嗯，KMP，我想了很久了，這是乙個非常巧妙的演算法！ 你看不懂百科全書什麼的，我就用手打......這是我的理解

為了便於解釋，我將長字串稱為文字字串，將短字串稱為目標字串

與文字字串相比，傳統的匹配演算法將目標字串逐個向右移動，而 KMP 則向右跳轉

我舉幾個例子。

例如，如果有乙個 ababaca 的目標字串，則當前位置與前 5 個匹配，即與 ababa 匹配，後兩個不匹配。

這說明文字字串的當前位置也是 ababa

顯然，不可能向右移動乙個位置，因為從目標字串中可以看出括號中的內容不等於 a（baba）。

並且可以向右移動兩個位置，因為你可以看到括號中的內容等於 ab，這意味著在移動兩個位置後，目標字串的前三個位置肯定是匹配的，因為它們在移動之前也匹配

例如，如果存在目標字串 abcab，則當前位置與前兩個 abs 匹配

然後你需要向右移動3個位置，因為括號中的內容與abc（ab）中的內容相同，移動後可以匹配

明白了？ 表達自己的能力有限......我不能說得更好......具體**網上有很多，在《演算法導論》裡也有我當初學的！

如果你明白了，我希望會有額外的積分，你的手累死了！！

如果你不明白，就問吧......

KMP演算法和BM演算法，分別是字首匹配和字尾匹配的經典演算法。

1. 由於路由表中的每個條目都指定了乙個網路，因此乙個目標位址可以匹配多個條目。 最顯式的條目，即具有最長子網掩碼的條目，稱為最長的字首匹配。

2.之所以這樣稱呼，是因為這個條目也是路由表中與目標位址高位匹配度最高的條目。

那麼，關於它們之間的聯絡，您告訴我們什麼？