KMP算法



前言

关于KMP算法，个人理解不深不透彻，通过几道题的训练，理解程度+0.01%，虽然本人不叙述整个算法的原理，但倒是可以推荐几篇博文给大家

  1. KMP详解
    https://www.cnblogs.com/zhangtianq/p/5839909.html
  2. KMP 循环节
    https://www.cnblogs.com/chenxiwenruo/p/3546457.html

剪花布条 | HDU - 2087

思路
裸的KMP算法

  #include <iostream>
  #include <cstdio>
  #include <cstring>
  using namespace std;
  const int N = 1005;

  int kmp_next[N];            //next数组

  void getNext(char* p){      //可保证k位置前的前缀与j位置前的后缀相同，因此可递推求出next数组
      kmp_next[0] = -1;
      int k = -1, j = 0;      //j管后缀，k管前缀
      int len = strlen(p);
      while(j < len){
          if(k == -1 || p[k] == p[j]){     //前缀为空或末尾能和前缀+1的位置匹配
              j++;                         //移动到下一位，写入下一位前面串的最大前后缀匹配长度
              k++;                         //前面串的最大前后缀匹配长度，也代表下次递推需满足p[k] == p[j]的k
              kmp_next[j] = (p[k] != p[j] ? k : kmp_next[k]);     //优化版的求next数组
          }else{
              //不匹配则回溯，因为对称性，所以下一步也只需要校验新的p[k]是否等于p[j]，能满足就能说明前后缀相同，不满足就继续回溯，
              //可能回溯到前缀为空，那么下一位前面串的最大前后缀匹配长度就为0
              k = kmp_next[k];
          }
      }
  }

  int kmpSearch(char* s, char* p){
      getNext(p);
      int slen = strlen(s), plen = strlen(p);
      int i = 0, j = 0;
      int cnt = 0;
      while(i < slen){
          //j == -1则说明前后缀不相同，直接置j为0，移动一整个串，s[i] == p[j]说明当前位匹配成功故位置都加1
          if(j == -1 || s[i] == p[j]){
              i++;
              j++;
          }else{
              j = kmp_next[j];    //相对移动，从后缀移动到前缀
          }

          if(j == plen){      //匹配完成
              cnt++;
              j = 0;          //j置0,继续新的匹配
          }
      }
      return cnt;
  }

  int main(){
      ios::sync_with_stdio(false);
      char s[N], p[N];
      while(cin >> s && s[0] != '#' && cin >> p){
          cout << kmpSearch(s, p) << endl;
      }
      return 0;
  }


Oulipo | HDU - 1686

题目大意
给定W串和T串，求T串中有多少个W串，允许重叠

思路
也是裸的KMP算法，难点就在于允许重叠，其实只需要在匹配完成一次后 j = knext[j]，移动到前缀就可以了

  #include <iostream>
  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  const int N = 1000006;
  typedef pair<int, int> pii;
  typedef long long ll;

  int knext[N];
  char s[N];
  char p[N];

  void getNext(char* p){
      knext[0] = -1;
      int k = -1, j = 0;
      int len = strlen(p);
      while(j < len){
          if(k == -1 || p[k] == p[j]){
              j++;
              k++;
              knext[j] = (p[k] != p[j] ? k : knext[k]);
          }else{
              k = knext[k];
          }
      }
  }

  int kmpSearch(char* s, char *p){
      getNext(p);
      int i = 0, j = 0;
      int ans = 0;
      int slen = strlen(s), plen = strlen(p);
      while(i < slen){
          if(j == -1 || s[i] == p[j]){
              i++;
              j++;
          }else{
              j = knext[j];
          }
          if(j == plen){
              ans++;
              j = knext[j];   //匹配完成后移动到前缀
          }
      }
      return ans;
  }

  int main(){
      int t;
      scanf("%d\n", &t);
      while(t--){
          scanf("%s\n%s\n", p, s);
          printf("%d\n", kmpSearch(s, p));
      }
      return 0;
  }


Cyclic Nacklace | HDU - 3746

题目大意
给定一字符串，问需要添加几个字符才能使得整个串由某一个不为本身的子串循环构成

思路
真的是有些感叹next数组的博大精深，具体思路其实可以看第二篇博文，写得蛮清楚的

  #include <iostream>
  #include <cstdio>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  const int N = 100005;
  typedef pair<int, int> pii;
  typedef long long ll;

  int knext[N];
  char p[N];

  void getNext(char* p){
      knext[0] = -1;
      int k = -1, j = 0;
      int len = strlen(p);
      while(j < len){
          if(k == -1 || p[k] == p[j]){
              j++;
              k++;
              knext[j] = k;      //要用未优化的求next数组
          }else{
              k = knext[k];
          }
      }
  }

  int main(){
      int t;
      scanf("%d", &t);
      while(t--){
          int ans;
          scanf("%s", p);
          getNext(p);
          int len = strlen(p);

          //最小循环节 = len - next[len]， 且 len%min_circle == 0 时该串由最小循环节循环构成
          int min_circle = len - knext[len];

          // len != min_circle 是为防止最小循环节是串本身时输出0
          if(len != min_circle && len%min_circle == 0){
              ans = 0;
          }else{
              ans = min_circle - len%min_circle;  // min_circle - len%min_circle 为所需补的长度，画图可知
          }
          printf("%d\n", ans);
      }
      return 0;
  }