Codeforces Round #246 (Div. 2) D. Prefixes and Suffixes

D. Prefixes and Suffixes

You have a string s = s₁s₂...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_is_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₁s₂...s_|s| (1 ≤ |s| ≤ 10⁵) — 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.

Sample test(s)

Input

ABACABA

Output

Input

AAA

Output

提意：求出满足前缀等于后缀的所有的子串的个数

sl:开始我是用的hash扫了下满足条件的前缀然后构造了一个ac自动机超时太大意了，搞得C题没敲完都。

原来此题是KMP的应用，其实就是两道原题的组合，关键是如何分类求出所有前缀的个数，首先用一个vis标记满足

条件的前缀，然后用next数组扫一边所有前缀此次扫描都是扫的以当前字符为结尾的最大的前缀，所以最后还要扫描一次

又叫我长见识了。。。。。 >_<

1 //codeforces Codeforces Round #246 (Div. 2) D
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <cmath>
6 #include <vector>
7 #include <list>
8 #include <queue>
9 using namespace std;
10 const int MAX = 1e6+10;
11 const int inf = 0x3f3f3f3f;
12 vector<pair<int,int> > ans;
13 int dp[MAX],next[MAX],vis[MAX],cnt[MAX];
14 char str[MAX];
15 int main()
16 {
17     //freopen("in","r",stdin);
18     //freopen("out","w",stdout);
19     while(scanf("%s",str+1)==1) {
20         int n=strlen(str+1);
21         next[1]=0; int j=0;
22         for(int i=2;i<=n;i++) {
23             while(str[i]!=str[j+1]&&j) j=next[j];
24             if(str[i]==str[j+1]) j++;
25             next[i]=j;
26         }
27
28         int x=n;
29         while(x) {
30             vis[x]=1; x=next[x];
31         }
32         for(int i=n;i>=1;i--) cnt[next[i]]++;
33        // for(int i=1;i<=n;i++) printf("%d ",cnt[i]); printf(" ");
34         for(int i=n;i>=1;i--) cnt[next[i]]+=cnt[i];
35         for(int i=1;i<=n;i++) if(vis[i]) ans.push_back(make_pair(i,cnt[i]));
36
37         printf("%d ",(int)ans.size());
38
39         for(int i=0;i<ans.size();i++) printf("%d %d ",ans[i].first,ans[i].second+1);
40     }
41     return 0;
42 }