字符串匹配算法：KMP算法

该算法用于查找字串在主串中的位置，使用普通算法时时间复杂度为O(m*n),而KMP算法的时间复杂度为O(m+n).

此处给出源码，有时间的话再写原理：

 #include <iostream>
 using namespace std;
 ​
 void GetNext(string str, int *next) //求next数组
 {
     int i = 1, j = 0;
     next[1] = 0;
     while (i < str.length() - 1)
     {
         if (j == 0 || str[i] == str[j])
         {
             i++;
             j++;
             next[i] = j;
         }
         else
             j = next[j];
     }
 }
 ​
 int KMP(string str, string t) //字符串匹配
 {
     int next[t.length()];
     GetNext(t, next);
     int i = 1, j = 1;
     while (i <= str.length() && j <= t.length())
     {
         if (j == 0 || str[i] == t[j])
         {
             i++;
             j++;
         }
         else
             j = next[j];
     }
     if (j > t.length())
         return i - t.length(); //成功
     else
         return 0; //失败
 }
 int main()
 {
     string str;
     cin >> str;
     str = '0' + str; //从1开始
     string t;
     cin >> t;
     t = '0' + t;                 //从1开始
     cout << KMP(str, t) << endl; //输出结果
     system("pause");
     return 0;
 }

该算法的求next数组部分使用了双指针的方法，思路十分巧妙，值得仔细分析学习。

标签：学习笔记, c/c++