D. Prefixes and Suffixes（KMP+dp）

- 日理万妓 2021-11-05 13:48 256阅读 0赞

参考博客：[https://blog.csdn.net/huanghongxun/article/details/53209004][https_blog.csdn.net_huanghongxun_article_details_53209004]  
题目链接：[http://codeforces.com/problemset/problem/432/D][http_codeforces.com_problemset_problem_432_D]

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 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 substring ci times. Print pairs li ci in the order of increasing li.  
Examples  
Input  
Copy

ABACABA

Output  
Copy

3  
1 4  
3 2  
7 1

分析：  
回忆一下next数组的含义。  
next\[i\]表示 str中以i结尾的非前缀子串 和 str的前缀 能够匹配的最大长度。  
也就是说next\[len\] 表示 子串（1-next\[len\]） 和子串（len-next\[len\] + 1，len）是完全匹配的。  
本题要求的是前缀和后缀完全匹配的长度，个数。  
next\[len\] 表示 子串（1-next\[len\]）（前缀） 和子串（len-next\[len\] + 1，len）（后缀）是完全匹配的。  
next\[next\[len\]\] 表示子串（1-next\[next\[len\]\]）（子串1到next\[len\]的前缀）和  
子串（next\[len\] - next\[next\[len\]\] + 1，next\[len\]）（子串1到next\[len\]的后缀） 是完全匹配的。  
那么，可得子串（1-next\[next\[len\]\]）和子串（len-next\[next\[len\]\]+1，len）是完全匹配的。  
通过归纳，可以证明  
如果从s\[1…n\]开始，那么s\[1…next\[n\]\]一定是字符串的前后缀，s\[1…next\[next\[n\]\]一定是s\[1…next\[n\]\]的前后缀，也肯定是字符串的前后缀。

接下来考虑dp方程。  
dp\[i\]表示字符串（1到i）在str中出现的次数。  
dp\[next\[i\]\] += dp\[i\] + 1；  
因为由上面的递推可知，1-next\[i\]出现的子串数，一定是1-i出现的次数 + 1。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    
    char str[100010];
    int dp[100010];
    int Next[100010];
    int Len[100010],top;
    
    int main()
    {
        scanf("%s",str + 1);
        int len = strlen(str + 1);
        for(int i = 0,j = 2; j <= len; ++ j)
        {
            while(i && str[j] != str[i + 1]) i = Next[i];
            if(str[i + 1] == str[j]) ++i;
            Next[j] = i;
        }
        int n = len;
        for(int i = n; i >= 1; i = Next[i])
        {
            Len[++top] = i;
        }
        for(int i = n; i >= 1; i --)
            dp[Next[i]] += ++ dp[i];
        printf("%d\n",top);
        for(int i = top; i >= 1; i --)
            printf("%d %d\n",Len[i],dp[Len[i]]);
    }

[https_blog.csdn.net_huanghongxun_article_details_53209004]: https://blog.csdn.net/huanghongxun/article/details/53209004
[http_codeforces.com_problemset_problem_432_D]: http://codeforces.com/problemset/problem/432/D