SPOJ NSUBSTR Substrings

Description
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

这道题就是要求长度为i的子串最多重复次数，可以用sa和sam来做，具体思想都是一样的..

这里就讲sam的做法吧，附上clj的解法：

说一下Right的求法吧，大概就是一个拓扑dp的一个过程，有一个性质：Right(s)等于所有fail连到s节点s’的Right(s’)的和+1

那么只看fail边，也就是suffix link，就会得到一棵拓扑树，把所有有用的节点Right变成1（什么是有用的节点呢，就是除了因为建sam而copy出来的点其余的点）..

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int Maxn = 250010;
int F[Maxn*2], d[Maxn*2], ch[Maxn*2][26], now, tot;
char s[Maxn]; int len;
int ans[Maxn];
queue <int> q;
int in_degree[Maxn*2], G[Maxn*2];
int _max ( int x, int y ){ return x > y ? x : y; }
int copy ( int p, int c ){int x = ++tot, y = ch[p][c];d[x] = d[p]+1;for ( int i = 0; i < 26; i ++ ) ch[x][i] = ch[y][i];F[x] = F[y]; F[y] = x;while ( ~p && ch[p][c] == y ){ ch[p][c] = x; p = F[p]; }return x;
}
void add ( int c ){int p, o;if ( p = ch[now][c] ){if ( d[p] != d[now]+1 ) copy ( now, c );now = ch[now][c];}else {d[o=++tot] = d[now]+1; p = now; now = o; G[o] = 1;while ( ~p && !ch[p][c] ){ ch[p][c] = o; p = F[p]; }F[o] = ~p ? ( d[p]+1 == d[ch[p][c]] ? ch[p][c] : copy ( p, c ) ) : 0;}
}
int main (){int i, j, k;F[0] = -1;scanf ( "%s", s+1 ); len = strlen (s+1);for ( i = 1; i <= len; i ++ ) add (s[i]-'a');for ( i = 1; i <= tot; i ++ ) in_degree[F[i]] ++;for ( i = 1; i <= tot; i ++ ){if ( !in_degree[i] ) q.push (i);}while ( !q.empty () ){int x = q.front (); q.pop ();G[F[x]] += G[x];in_degree[F[x]] --;if ( !in_degree[F[x]] ) q.push (F[x]); }for ( i = 1; i <= tot; i ++ ) ans[d[i]] = _max ( G[i], ans[d[i]] );for ( i = len-1; i >= 1; i -- ) ans[i] = _max ( ans[i], ans[i+1] );for ( i = 1; i <= len; i ++ ) printf ( "%d\n", ans[i] );return 0;
}