题面

题目描述

给你一个字符串s，对于s的每一个前缀，如果它也是s的一个后缀，输出这个前缀在s中出现了多少次。

输入格式

一个字符串s（长度<=100000）；只含有大写字母。

输出格式

第一行输出一个整数k——满足条件的前缀个数；

接下来k行，每行两个整数l，c，代表长度为l的前缀满足条件，在整个字符串中出现了c次。按l从小到大输出。

样例

Input1

ABACABA

Output1

31 43 27 1

Input2

AAA

Output2

31 32 23 1

题解

考虑每一个前缀\(str[0 .. i]\), 假如它也是字符串的后缀的话, 则有\(str[len - i - 1 .. len - 1] = str[0 .. i]\), 即\(match[len - i - 1] = i\).

对于每一个\(i\)判断是否存在\(match[len - i - 1] = i\)即可, 并统计整个\(match[]\)数组中\(match[n] >= i\)的数量即可.

#include 
    
     #include 
     
      #include 
      
        const int L = (int)1e5; int main(){    static char str[L];    scanf("%s", str);    int len = strlen(str);    static int mch[L];    mch[0] = len - 1, mch[1] = -1;    for(; mch[1] + 1 < len && str[mch[1] + 1] == str[1 + mch[1] + 1]; ++ mch[1]);    int p = 1, mx = p + mch[p];    for(int i = 2; i < len; ++ i)    {        mch[i] = std::max(std::min(mx - i, mch[i - p]), -1);        for(; i + mch[i] < len && str[mch[i] + 1] == str[i + mch[i] + 1]; ++ mch[i]);        if(i + mch[i] > mx)            p = i, mx = i + mch[i];    }    static int sum[L];    memset(sum, 0, sizeof(sum));    for(int i = 0; i < len; ++ i)        if(~ mch[i])            ++ sum[mch[i]];    for(int i = len - 1; i; -- i)        sum[i - 1] += sum[i];    int cnt = 0;    for(int i = 0; i < len; ++ i)        if(mch[len - i - 1] == i)            ++ cnt;    printf("%d\n", cnt);    for(int i = 0; i < len; ++ i)        if(mch[len - i - 1] == i)            printf("%d %d\n", i + 1, sum[i]);}