#include <stdio.h> #include <string.h> #include <stdlib.h>typedef int Position; //返回數組下標 #define NotFound -1 void BuildMatch( char *pattern, int *match ) {Position i, j;int m = strlen(pattern);match[0] = -1; //match[0]肯定是-1for ( j=1; j<m; j++ ) { //對每一個下標計算match值i = match[j-1]; //把前一個match值記在i里while ( (i>=0) && (pattern[i+1]!=pattern[j]) )i = match[i]; //讓i回退if ( pattern[i+1]==pattern[j] )match[j] = i+1;else match[j] = -1;} }Position KMP( char *string, char *pattern ) {int n = strlen(string); //得到字符串長度int m = strlen(pattern); //得到模式串長度Position s, p, *match;if ( n < m ) return NotFound;match = (Position *)malloc(sizeof(Position) * m); //定義整型數組matchBuildMatch(pattern, match); //計算match的值s = p = 0; //一開始指向起點0while ( s<n && p<m ) { //s和p都還沒到結尾if ( string[s]==pattern[p] ) {s++; p++; //相配則一起往前移動}else if (p>0) p = match[p-1]+1; //不相配，p指針往回移else s++; //p=0，第一個字符就不匹配，s指針往前移}return ( p==m )? (s-m) : NotFound; //p到結尾，匹配成功，返回匹配上的位置s-m。否則匹配失敗 }int main() {char string[] = "This is a simple example.";char pattern[] = "simple";Position p = KMP(string, pattern);if (p==NotFound) printf("Not Found.\n");else printf("%s\n", string+p);return 0; }

代碼來自中國大學MOOC浙江大學版數據結構

總結

以上是生活随笔為你收集整理的【数据结构】KMP算法（c语言）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。