spoj8222 NSUBSTR - Substrings

spoj8222 NSUBSTR - Substrings

​​ 题意翻译 你得到一个字符串，最多由25万个小写拉丁字母组成。我们将 F(x)定义为某些长度X的字符串在s中出现的最大次数，例如字符串’ababaf’- F(x)，因为有一个字符串’ABA’出现两次。你的任务是输出 F(x)每一个I，以使1<=i<=|S|. 题目描述 You are given a string S which consists of 250000 lowercase latin letters at most. We define F(x) as the maximal number of times that some string with length x appears in S. For example for string ‘ababa’ F(3) will be 2 because there is a string ‘aba’ that occurs twice. Your task is to output F(i) for every i so that 1<=i<=|S|. 输入输出格式 输入格式： String S consists of at most 250000 lowercase latin letters. 输出格式： Output |S| lines. On the i-th line output F(i). 输入输出样例 输入样例#1： 复制 ababa 输出样例#1： 复制 3 2 2 1 1 我的做法仍然是首先拓扑排序 然后直接倒推一下dp 注意可能最后dp数组需要倒推一遍 因为我拓扑排序的时候处理出的dp数组应该都只是针对那个节点对应的right集合的最长的那个值 update 重新思考一下觉得dp数组并不需要倒着推 因为仔细观察拓扑排序的时候即可知道我一定是大的更新小的 那么只有在par树上才会存在这样的对答案有贡献的结果 那么即使一个节点在par树上可能和上一个节点的长度差距很大 但是因为right集合是有包含关系的所以转移到我的情况上的那些节点 如果有错qwq请联系本蒟蒻 联系方式在(elijahqi.win)的个人资料页

#include#include#include#define N 510000#define rg registerusing namespace std;char s[N>>1];int dp[N>>1],size[N],c[N],rk[N];int len[N],fa[N],ch[N][26],root=1,cnt=1,last=1;inline void insert1(int x){ int np=++cnt,p=last;fa[np]=p;len[np]=len[p]+1; for (;p&&!ch[p][x];p=fa[p]) ch[p][x]=np; if (!p)fa[np]=root;else{ int q=ch[p][x];if (len[p]+1==len[q]) fa[np]=q;else{ int nq=++cnt;memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q]; fa[q]=fa[np]=nq;len[nq]=len[p]+1;for (;p&&ch[p][x]==q;p=fa[p]) ch[p][x]=nq; } }last=np;size[np]=1;}int main(){// freopen("spoj8222.in","r",stdin); scanf("%s",s);int le=strlen(s); for (rg int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。