SZUacm集训字符串基础总结 ：KMP, EXKMP, Manracher, Trie树，字符串的hash; 附带一写常见的运用技巧，邝斌大佬的板子和例题

第一部分 字符串的匹配<-------->KMP

模式匹配:子串的定位运算称为串的模式匹配或串匹配。

假设有两个串S，T，设S为主串，也称正文串，T为子串，也称为模式，在主串S中查找与模式T相匹配的子串，如果查找成功，返回匹配的子串第1个字符在主串中的位置。最笨的办法就是穷举所有S的所有子串，判断是否与T匹配。该算法称为BF(Brute Force)算法，Brute Force的意思是蛮力，暴力穷举。

Knuth、Morris和Pratt对 该算法进行了改进，称为KMP算法。

i指向的字符前面的两个字符和T串中j指向的字符前面两个字符一-模一 样，因为它们一直相等，才会i++，j++走到当前的位置。只需要在T串本身比较就可以了。就是当不匹配的时候就回退，回退最长公共前缀的位置(pmt该位置(0~i)的子串和t串最长公共前缀（对于aba 末尾的a和第一个a相同）)

回退位置next[]的求解方法:

本质上就是模式串的每一个前缀的后缀和模式串前缀的最长匹配长度

算法复杂性分析:

设S、T串的长度分别为n、m。KMP算法的特点就是，i不回退，当S[j]tT[j时， j回退到nextj]，重新开始比较。最坏情况下扫描整个S串, 其时间复杂度为0(n)。计算next数组需要扫描整个T串，其时间复杂度为0(m),因此总的时间复杂度为0(n+m)。

下面看代码

void Getnext(int next[],String t)
{
   int j=0,k=-1;
   next[0]=-1;
   while(j<t.length-1)
   {
      if(k == -1 || t[j] == t[k])
      {
         j++;k++;
         next[j] = k;
      }
      else k = next[k];//此语句是这段代码最反人类的地方，如果你一下子就能看懂，那么请允许我称呼你一声大神！
   }
}

int KMP(String s,String t)
{
   int next[MaxSize],i=0;j=0;
   Getnext(t,next);
   while(i<s.length&&j<t.length)
   {
      if(j==-1 || s[i]==t[j])
      {
         i++;
         j++;
      }
      else j=next[j];               //j回退。。。
   }
   if(j>=t.length)
       return (i-t.length);         //匹配成功，返回子串的位置
   else
      return (-1);                  //没找到
}

这篇博客写的比较好

KMP的扩展引用

就是求一个字符串的循环节(next数组的应用)

序更qwq()