首页 > 代码库 > spoj 8222
spoj 8222
8222. Substrings
Problem code: NSUBSTR
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|.
Input
String S consists of at most 250000 lowercase latin letters.
Output
Output |S| lines. On the i-th line output F(i).
Example
Input:
ababa
Output:
3
2
2
1
1
题目大意:
给出一个字符串(len <= 2.5e5),求出这个串中,长度为 i (1 <= i <= len) 并且出现次数最多的串,并且输出出现次数.
思路:
根据Spoj1811所提出的这个性质,我们现在SAM上自己匹配自己.得到一个出事的状态.
不难发现.当这个点的后继(parnet关系)出现了之后,这点所表示的字符串也同样的出现了.
那么这个点所表示的字符串也出现了.
那么这个点所表示的字符串出现了多少次呢?
其实是这个点的后缀节点的和.......
然后我们就能够统计这个东西了.
我有个地方没有弄明白,就是,这个点所能够接受的字串有若干个....为什么只用判断这个最长的串呢?
一点初步的想法: 因为par表示这个点的所有的串的最长公共后缀,所以我们能够保证par至少 sz[x] 次,
虽然不知到为什么这个par表示的其他串不用计算,但是似乎在par更新par_par 的时候会计算进去.
根据意识流大法......好像是这么回事....下次再补上吧.
代码也就顺理成章了.
1 #include<cstdlib> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 using namespace std; 6 const int maxn = (int)2.55e5, sigma = 26; 7 char str[maxn]; 8 int cnt[maxn]; 9 int id[maxn];10 int ans[maxn];11 int cmp(int,int);12 struct Sam{13 int ch[maxn * 2][sigma],par[maxn * 2],stp[maxn * 2];14 int sz,last;15 void init(){16 sz = last = 1;17 memset(ch,0,sizeof(ch));18 memset(par,0,sizeof(par));19 memset(stp,0,sizeof(stp));20 }21 void add(int c){22 stp[++sz] = stp[last] + 1;23 int p = last, np = sz;24 for(; !ch[p][c]; p = par[p]) ch[p][c] = np;25 if(p == 0) par[np] = 1;26 else{27 int q = ch[p][c];28 if(stp[q] != stp[p] + 1){29 stp[++sz] = stp[p] + 1;30 int nq = sz;31 memcpy(ch[nq],ch[q],sizeof(ch[q]));32 par[nq] = par[q];33 par[q] = par[np] = nq;34 for(; ch[p][c] == q; p = par[p]) ch[p][c] = nq;35 }36 else par[np] = q;37 }38 last = np;39 }40 void ins(char *pt){41 int i;42 init();43 for(i = 0; pt[i]; ++i) add(pt[i] - ‘a‘);44 }45 void solve(char *pt){46 memset(id,0,sizeof(id)); memset(cnt,0,sizeof(cnt)); memset(ans,0,sizeof(ans));47 int i,p = 1;48 for(i = 1; i <= sz; ++i) id[i] = i;49 sort(id+1,id+sz+1,cmp);50 for(i = 0; pt[i]; ++i)51 ++cnt[p = ch[p][pt[i] - ‘a‘]];52 for(i = 1; i <= sz; ++i){53 ans[stp[id[i]]] = max(ans[stp[id[i]]], cnt[id[i]]);54 if(par[id[i]] != 0) cnt[par[id[i]]] += cnt[id[i]];55 }56 for(i = 0; pt[i]; ++i) printf("%d\n",ans[i + 1]);57 }58 }sam;59 int cmp(int x,int y){60 return sam.stp[x] > sam.stp[y];61 }62 int main()63 {64 freopen("substr.in","r",stdin);65 freopen("substr.out","w",stdout);66 while(scanf("%s",str) != EOF){67 sam.ins(str);68 sam.solve(str);69 }70 return 0;71 }
spoj 8222