#include <iostream>

#include <vector>

using namespace std;

//字符串搜索算法：KMP

//构造next数组(前缀函数&构造匹配表&computeLPSArray)

vector<int> getNext(string s){

   vector<int> ne(s.size()+1,0);

   int i=0;

   int j=-1;

   ne[i]=j;

   while(i<s.size()){

       if(j==-1||s[i]==s[j]) ne[++i]=++j;

       else j=ne[j];

   }

   return ne;

}

//KMP匹配过程(在s中搜索p)

vector<int> KMPSearch(string s,string p){

   vector<int> ans;

   vector<int> ne=getNext(p);

   int i=0,j=0;

   while(i<s.size()){

       while(j>0&&s[i]!=p[j]) j=ne[j];

       if(s[i]==p[j]) j++;

       if(j==p.size()) ans.push_back(i-j+1);

       i++;

   }

   return ans;

}

int main(){

   string s="abababcab";

   string p="ab";

   vector<int> ans=KMPSearch(s,p);

   for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";

   return 0;

}

1467:KMP求最小循环节

cabcabca

cabca

  cabca

  相同前后缀的长度

最小循环节长度=字符串长度-相同前后缀的长度

abcdeabc

abc  

    abc

abcde 就是循环节

解决方案：n-nt[n]

1468:将本字符串的所有前缀找到

所有前缀对应的最大周期累加求和即答案【最大周期与上一题正相反】

babababa

前缀

b    0

ba   0

bab  ba 2 b 1 3-1=2

baba ba 2 ba 2 4-2=2

babab  baba 4 b 1 5-1=4

bababa baba 4 ba 2 6-2=4

bababab  bababa 6

babababa bababa 6

0+0+2+2+4+4+6+6=24

next数组求的是当前下标前面的字符串的最长相同前缀后缀的长度

本题求的是当前下标前面的字符串的最短相同前缀后缀的长度

cabcabca ca 8-2=6