Prefixes and Suffixes CodeForces - 432D （KMP的next数组的应用）（图解）-白红宇

Prefixes and Suffixes CodeForces - 432D （KMP的next数组的应用）（图解）

阅读量：6848 次

发布时间：2019-06-26

本文共 2387 字，大约阅读时间需要 7 分钟。

Prefixes and Suffixes

You have a string s = 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 ≤ i ≤ j ≤ |s|) of string s is string sisi + 1...sj.

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 s1s2...s|s| (1 ≤ |s| ≤ 105) — 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 lici. Numbers li ci mean that the prefix of the length li matches the suffix of length li and occurs in string s as a substring ci times. Print pairs li ci in the order of increasing li.

Examples

Input

ABACABA

Output

31 43 27 1

Input

AAA

Output

31 32 23 1

题目大意：

给出一个字符串“对于字符串s中与后缀匹配的前缀，输出它在字符串s中作为子串的次数。”谷歌翻译的结果，我觉得意思已经很明确了，不作赘述。

思路：

这个题目很容易让我们想到KMP的自匹配。nxt[len]就是最长的那个前后匹配的串，但是我们的问题来了，如何得出长度更短的前后匹配的串呢？

（此时红色的串是前后匹配的）

我们不妨来看看nxt[nxt[len]]我们知道他是原数组中前nxt[len]个元素的数组中前后匹配的串的长度，也就是：

绿色的串

但是考虑到前后的红色部分也是相同的，所以所有的相等的绿色串应该就是

（图中的绿色的串都是相等的）

Amazing！这样首尾就也是相等的了！充分证明了所有的前后相等的子串就是不断地求自己的next。当然，必要性可以简单证明，这里就不赘述。

至于子串在自身中的重复次数，只需要对每个位置i的next[i]的数量（以next结尾的字符串的数量）的都加上他们自身的数量即可。

具体见代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #define endl '\n'#define sc(x) scanf("%d",&x)using namespace std;const int size=1e5+5;int nxt[size];char s[size];int num[size],ans[size];int mny[size];int cnt=0;int m;void getnext(){ int i,j; nxt[0] = j = -1; i = 0; while(i < m) { while(j!=-1&&s[j]!=s[i]) j = nxt[j]; nxt[++i] = ++j; }}void query(){ cnt=0; fill(num,num+m+1,1); for(int i=m;i>=1;i--) { if(nxt[i]!=-1) num[nxt[i]]+=num[i]; } for(int i=m;i!=0;i=nxt[i]) { ans[cnt]=i; mny[cnt]=num[i]; cnt++; } //ans[cnt]=0;mny[cnt++]=num[0];}int main(){ while(cin>>s) { m=strlen(s); getnext(); query(); cout<
               
                <
                
                 =0;i--) { printf("%d %d\n",ans[i],mny[i]); } } return 0;}

转载于:https://www.cnblogs.com/fly-white/p/10092745.html

你可能感兴趣的文章