codeforces432D Prefixes and Suffixes(kmp+dp)

转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud

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_ic_i. Numbers l_ic_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_ic_i in the order of increasing l_i.

Sample test(s)

Input

ABACABA

Output

Input

AAA

Output

题意：

　　给出一个字符串，问每种既是前缀，又是后缀的字符串出现的次数kmp+dp,利用kmp求出所有的前后缀，考虑到若第i位既是前缀又是后缀，则kmp中的p[i]位也一定是，由此可以得到一个状态转移的方程dp[p[i]]+=dp[i],初始化所有的dp[i]=1，因为还包括它本身。

我队友curs0r是用后缀数组做的。。。。。。

 #include <iostream>

 #include <sstream>

 #include <ios>

 #include <iomanip>

 #include <functional>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <list>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <set>

 #include <map>

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <climits>

 #include <cctype>

 using namespace std;

 #define XINF INT_MAX

 #define INF 0x3FFFFFFF

 #define MP(X,Y) make_pair(X,Y)

 #define PB(X) push_back(X)

 #define REP(X,N) for(int X=0;X<N;X++)

 #define REP2(X,L,R) for(int X=L;X<=R;X++)

 #define DEP(X,R,L) for(int X=R;X>=L;X--)

 #define CLR(A,X) memset(A,X,sizeof(A))

 #define IT iterator

 typedef long long ll;

 typedef pair<int,int> PII;

 typedef vector<PII> VII;

 typedef vector<int> VI;

 #define MAXN 100010

 char s[MAXN];

 int p[MAXN];

 int dp[MAXN];

 int vis[MAXN];

 void getp()

 {

     p[]=;

     int len=strlen(s+);

     for(int i=,j=;i<=len;i++)

     {

         while(j>&&s[j+]!=s[i])j=p[j];

         if(s[j+]==s[i])j+=;

         p[i]=j;

     }

 }

 int main()

 {

     ios::sync_with_stdio(false);

     while(cin>>s+)

     {

         int len=strlen(s+);

         getp();

         for(int i=;i<=len;i++)

         {

             dp[i]=;

         }

         int i=len;

         int k=;

         while(i)

         {

             vis[k]=i;

             k++;

             i=p[i];

         }

         for(i=len;i>;i--)

         {

             dp[p[i]]+=dp[i];

         }

         cout<<k<<endl;

         for(i=k-;i>=;i--)

         {

             cout<<vis[i]<<" "<<dp[vis[i]]<<endl;

         }

     }

     return ;

 }

代码君

秒客网

codeforces432D Prefixes and Suffixes(kmp+dp)

相关文章