题目大意：给出一个字符串，求全部既是前缀串又是后缀串的字符串出现了几次。

解题思路：依据性质能够依据KMP算法求出全部的前后缀串，然后利用dp求解，dp[i]表示从1到i这个子串出现过的次数。

转移方程dp[jump[i]]+=dp[i]。

随意一个dp[i]的初始状态应该是1。

#include 
     
      #include 
      
       const int N = 1e5+5;int n, jump[N], c, r[N], dp[N];char str[N];void getJump() {    int k = 0;    n = strlen(str+1);    for (int i = 2; i <= n; i++) {        while (k && str[i] != str[k+1])            k = jump[k];        if (str[i] == str[k+1])            k++;        jump[i] = k;    }}int main () {    scanf("%s", str+1);    getJump();    c = 0;    for (int i = jump[n]; i; i = jump[i]) {        r[c] = i;        c++;    }    memset(dp, 0, sizeof(dp));    for (int i = n; i; i--) {        dp[i]++;        dp[jump[i]] += dp[i];    }    printf("%d\n", c+1);    for (int i = c-1; i >= 0; i--)        printf("%d %d\n", r[i], dp[r[i]]);    printf("%d %d\n", n, dp[n]);    return 0;}
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。