KMP算法介绍

KMP算法是一种字符串匹配算法，它可以在一个已排序的字符串中快速查找另一个字符串的位置。下面是一个使用C语言实现KMP算法的示例代码：

#include <stdio.h>  
#include <string.h>  
  
void computeLPSArray(char* pat, int M, int* lps)  
{  
    int len = 0;  
    int i = 1;  
    lps[0] = 0;  
  
    while (i < M) {  
        if (pat[i] == pat[len]) {  
            len++;  
            lps[i] = len;  
            i++;  
        }  
        else {  
            if (len != 0) {  
                len = lps[len-1];  
            }  
            else {  
                lps[i] = 0;  
                i++;  
            }  
        }  
    }  
}  
  
void kmp(char* pat, char* txt)  
{  
    int M = strlen(pat);  
    int N = strlen(txt);  
    int lps[M];  
    computeLPSArray(pat, M, lps);  
  
    int i = 0;  
    int j = 0;  
    while (i < N) {  
        if (pat[j] == txt[i]) {  
            j++;  
            i++;  
        }  
  
        if (j == M) {  
            printf("Pattern found at index %d\n", i-j);  
            j = lps[j-1];  
        }  
        else if (i < N && pat[j] != txt[i]) {  
            if (j != 0) {  
                j = lps[j-1];  
            }  
            else {  
                i = i+1;  
            }  
        }  
    }  
}  
  
int main()  
{  
    char txt[] = "ABCABCDABCDABD";  
    char pat[] = "ABCDABD";  
    kmp(pat, txt);  
    return 0;  
}

c#include <stdio.h>  #include <string.h>    void computeLPSArray(char* pat, int M, int* lps)  {      int len = 0;      int i = 1;      lps[0] = 0;        while (i < M) {          if (pat[i] == pat[len]) {              len++;              lps[i] = len;              i++;          }          else {              if (len != 0) {                  len = lps[len-1];              }              else {                  lps[i] = 0;                  i++;              }          }      }  }    void kmp(char* pat, char* txt)  {      int M = strlen(pat);      int N = strlen(txt);      int lps[M];      computeLPSArray(pat, M, lps);        int i = 0;      int j = 0;      while (i < N) {          if (pat[j] == txt[i]) {              j++;              i++;          }            if (j == M) {              printf("Pattern found at index %d\n", i-j);              j = lps[j-1];          }          else if (i < N && pat[j] != txt[i]) {              if (j != 0) {                  j = lps[j-1];              }              else {                  i = i+1;              }          }      }  }    int main()  {      char txt[] = "ABCABCDABCDABD";      char pat[] = "ABCDABD";      kmp(pat, txt);      return 0;  }

在上面的代码中，我们首先定义了一个computeLPSA然后，我们定义了一个kmp函数，用于在文本串中查找模式串的位置。在kmp函数中，我们首先计算模式串的最长公共前缀和最长公共后缀数组，然后使用两个指针i和j分别指向文本串和模式串的当前位置。在每次循环中，我们比较当前位置的字符和模式串的对应位置的字符是否相等，如果相等，则将j指向下一个位置，否则将i指向下一个位置。如果j等于M，则表示找到了模式串的位置，输出该位置的索引，并将j指向下一个位置；否则，如果i小于N，且当前字符不等于模式串的对应字符，则将j指向下一个位置，否则将i指向下一个位置。最后，我们在main函数中调用kmp函数，并输出查找到的模式串的位置。

需要注意的是，在实际应用中，我们需要根据具体的需求选择合适的算法和数据结构，并进行适当的优化和调试。同时，我们还需要注意代码的可读性和可维护性，避免出现重复代码和错误