首页 > 代码库 > SPOJ_NSUBSTR
SPOJ_NSUBSTR
题目意思是给你一个字符串,f[x]是长度为x的子串中,出现个数最多的那个串的出现次数。
给出原串,依次输出f[1],f[2],……。
后缀自动机。对于某一个状态,right[]值的大小就是出现的次数,而且是对于长为step[]的子串的出现次数。
因为小于step值的串在前面已经加了,在pre指针线上面的状态要把当前数量累加上去即可。
不过注意这里要先拓扑排序,这样才能保证更新的正确性。恩,很实用很不错的一种拓扑排序方式。新技能get。
召唤代码君:
#include <iostream>#include <cstdio>#define maxn 500500using namespace std;int next[maxn][26],pre[maxn],step[maxn],dp[maxn],g[maxn],Q[maxn],cnt[maxn];int N,last,p,q,np,nq;char s[maxn];void insert(int x,int m){ p=last,np=++N,step[np]=m,last=np,g[np]++; while (p!=-1 && next[p][x]==0) next[p][x]=np,p=pre[p]; if (p==-1) return ; q=next[p][x]; if (step[q]==step[p]+1) { pre[np]=q; return; } nq=++N,step[nq]=step[p]+1,pre[nq]=pre[q]; for (int i=0; i<26; i++) next[nq][i]=next[q][i]; pre[np]=pre[q]=nq; while (p!=-1 && next[p][x]==q) next[p][x]=nq,p=pre[p];}int main(){ pre[0]=-1; scanf("%s",s); for (int i=0; s[i]; i++) insert(s[i]-‘a‘,i+1); for (int i=1; i<=N; i++) cnt[step[i]]++; for (int i=1; i<=N; i++) cnt[i]+=cnt[i-1]; for (int i=1; i<=N; i++) Q[cnt[step[i]]--]=i; for (int i=N; i>=1; i--) dp[step[Q[i]]]=max(dp[step[Q[i]]],g[Q[i]]),g[pre[Q[i]]]+=g[Q[i]]; for (int i=1; s[i-1]; i++) printf("%d\n",dp[i]); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。