Codeforces 432D. Prefixes and Suffixes (DP + next数组)

Description
You have a string s?=?s 1 s 2…s |s|, where |s| is the length of string s, and s i its i-th character.

Let’s introduce several definitions:

A substring s[i…j] (1?≤?i?≤?j?≤?|s|) of string s is string s i s i?+?1…s j.
The prefix of string s of length l (1?≤?l?≤?|s|) is string s[1…l].
The suffix of string s of length l (1?≤?l?≤?|s|) is string s[|s|?-?l?+?1…|s|].
Your task is, for any prefix of string s which matches a suffix of string s, print the number of times it occurs in string s as a substring.

Input
The single line contains a sequence of characters $s_1 s_2...s_|s| (1?≤?|s|?≤?10^5)$— string s. The string only consists of uppercase English letters.

Output
In the first line, print integer $k (0?≤?k?≤?|s|)$ — the number of prefixes that match a suffix of string s. Next print $k$ lines, in each line print two integers $l_i c_i$. Numbers $l_i c_i$ mean that the prefix of the length $l_i$ matches the suffix of length $l_i$ and occurs in string $s$ as a substring $c_i$ times. Print pairs $l_i$ $c_i$ in the order of increasing $l_i$.

Examples
Input
ABACABA
Output
3
1 4
3 2
7 1

Input
AAA
Output
3
1 3
2 2
3 1

Solution
统计有多少对公共前后缀，以及他们在整个串中的出现次数
先求出next数组，从最后开始沿着next数组向前跳，这样就能得到所有的匹配前后缀
再设dp[i] = 长度为i的前缀出现的次数
转移方程：
$dp[nex[i]]~+=~dp[i]$

Hint
Codeforces 126B ：求一个串中是否存在一个子串，既是前缀，又是后缀，也是非前后缀
这题也可以采用相同的解法

Code

int nex[maxn];
char s[maxn];
void find_nex(int m){int i,j;j = nex[1] = 0;i = 2;while(i <= m){while(j && s[i] != s[j+1]) j = nex[j];if(s[i] == s[j+1]) j++;nex[i++] = j;}
}
int ans[maxn];
int dp[maxn];
int main(){scanf("%s",s+1);int n = strlen(s+1);find_nex(n);int tot = 0;for(int i = n;i > 0;i = nex[i]){ans[++tot] = i;}for(int i = n;i > 0;--i){dp[i]++;dp[nex[i]] += dp[i];}printf("%d\n", tot);for(int i = tot;i > 0;--i){printf("%d %d\n", ans[i], dp[ans[i]]);}return 0;
}