KMP算法,没写出来,完全不理解NEXT数组。现在理解了很多

答案都在程序中

,不过这个思想真的很神奇,

还有毛语不好,一直没看懂题目,现在懂了,

大概是:S中前缀等于后缀,求其长度,和其在S中出现了几次,

KMP可以直接求出各个长度,但是求次数真的真的很神奇:

/*

CJT:第一份KMP算法,呜呜
我的理解:先求出next数组,next 数组的含义是:可以跳过的
个数,也是前缀的数
先求出tot,答案数,
然后求数组中有多少个可以substring
因为nexts是关于求对称的个数,所以
可以用来后面的求个数 */
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
string s;
int vis[],tot;
int ans[],next[]; void kmp()
{
    int k=-,i=;
    next[]=-;
    while (i<s.size())
    {
      if (k==-||s[i]==s[k])
      {
          ++k,++i;
          next[i]=k;
      }
      else k=next[k];
    }
} int main()
{
    cin>>s;
    kmp();
    int l=s.size();
    int id=l;
    while (id)
    {
        ++tot;
        vis[id]=;
        id=next[id];
    }
    for (int i=;i<=l;i++) ans[i]=;
    
    for (int i=l;i>=;i--)
    ans[next[i]]+=ans[i];//这里很难写
    
    cout<<tot<<endl;
    for (int i=;i<=l;i++)
    if (vis[i]) cout<<i<<" "<<ans[i]<<endl;
    return ;
}
05-04 02:06