Codeforces 432 D. Prefixes and Suffixes

ㄦ 灞 MP ....

You have a string s em>s1s2...s|s|, where |s| is the length of string s, and si its i-th character.

Let's introduce several definitions:

• A substring s[i..j] (1 em>i em>j s|) of string s is string sisi #43; ...sj.
• The prefix of string s of length l (1 em>l s|) is string s[1..l].
• The suffix of string s of length l (1 em>l s|) is string s[|s| em>l #43; ..|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 s1s2...s|s| (1 s| 05) string s. The string only consists of uppercase English letters.

  Output

  In the first line, print integer k (0 em>k s|) the number of prefixes that match a suffix of string s. Next print k lines, in each line print two integers li ci. Numbers li ci mean that the prefix of the length li matches the suffix of length li and occurs in string s as a substringci times. Print pairs li ci in the order of increasing li.

  Sample test(s) input

  ABACABA
  

  output

  3
  1 4
  3 2
  7 1
  

  input

  AAA
  

  output

  3
  1 3
  2 2
  3 1

  
  

  
  

  #include 
      
       
  #include 
       
         #include 
        
          #include 
         
           using namespace std; const int maxn=100100; char T[maxn],P[maxn]; int next[maxn],ex[maxn]; void pre_exkmp(char P[]) { int m=strlen(P); next[0]=m; int j=0,k=1; while(j+1
          
           >P; pre_exkmp(P); int n=strlen(P); for(int i=0;i
           
            =0;i--) { sum[lisan[i]]=sum[lisan[i+1]]+pos[lisan[i]]; } for(int i=0;i