Codeforces 432 D.Prefixes and Suffixes (Z Algorithm) / (KMP+dp)

题目链接：

http://codeforces.com/contest/432/problem/D

题意：

给你一个字符串，找到所有前缀与后缀相同的位置，以及这个前缀在整个字符串出现的次数

ABACABA ==> pre: A suf:A ---> 1 4 在1这个位置有相同的后缀，A出现了4次

　　　　　　　pre: ABA suf: ABA ----> 3 2 在3这个位置有相同的后缀，ABA出现了2次

思路：

方法一: Z Algorithm 新技能get http://courses.csail.mit.edu/6.006/spring11/lectures/lec18-extra.pdf

　　　　Z Algorithm z[i]表示第i个位置与前缀匹配了多少个字符
　　　　比如 A B C D E A B C D E A B C
　　　　 0 0 0 0 0 8 0 0 0 0 3 0 0

　　　　我们用非常巧妙的方式得到了z数组 [ 虽然不太懂，感觉和求manacher的回文半径有点相似]

　　　　那么当z[n-i-1]==i+1 的时候，它就是答案，就是说第n-i+1个位置延伸到最后了，也就是后缀与前缀匹配了，对于其他不等的z，我们对匹配的相同长度的计数

　　　　逆推回去得到出现几次的答案，看代码把。。

方法二： KMP+dp。对next数组，理解深了一点

　　　　ABABCDABAB

　　　　p next

　　　　0 0
　　　　1 0
　　　　2 0
　　　　3 1
　　　　4 2
　　　　5 0
　　　　6 0
　　　　7 1
　　　　8 2
　　　　9 3
　　　　10 4

　　　　每次从最后往前跳，比如从第10个位置跳到了第4个位置，那么前四个与后四个是一样的，对于新的串ABAB, 相当于ABAB还是后缀，再继续跳，直到跳到0

　　　　所以跳了几次，就有几个位置与后缀匹配了。

　　　　然后 dp，dp[i]表示从1到 i 这个子串出现过的次数，转化为算next[i]出现了几次，从后往前推 dp[Next[i]] += dp[i]; 初始dp[i]=1

代码一：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//////////////////////////////////////////////////////////////////////////
const int maxn = 1e5+10;

string s;
// Z Algorithm z[i]表示第i个位置与前缀匹配了多少个字符
// 比如 ABCDEABCDEABC
//      0000080000300
int z[maxn],a[maxn],f[maxn];

int main(){
    cin >> s;
    int n = s.size();
    int l=0,r=0;
    for(int i=1; i<=n-1; i++){
        if(i <= r) z[i] = min(r-i+1,z[i-l]);
        while(i+z[i]<n && s[z[i]]==s[i+z[i]]) z[i]++;
        if(i+z[i]-1 > r){
            l = i;
            r = i+z[i]-1;
        }
    }
    for(int i=0; i<n; i++) a[z[i]]++; // 与前缀匹配的相同长度的有几个
    for(int i=n; i>=0; i--){
        f[i] += f[i+1]; // f数组表示匹配长度为i的有几个[不包括前缀], 要逆推，累加，因为长度长的匹配上了，那也一定符合长度短的。
        f[i] += a[i];
    }
    int cnt = 0;
    for(int i=0; i<n; i++){
        if(z[n-i-1] == i+1)
            cnt++;
    }
    cnt++; // 整个串， z[0]=0!=n, 所以没算进答案中
    cout << cnt << endl;
    for(int i=0; i<n; i++){
        if(z[n-i-1]==i+1){
            cout << i+1 << " " << f[i+1]+1 << endl;
        }
    }
    cout << n << " " << 1 << endl;

    return 0;
}

代码二：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//////////////////////////////////////////////////////////////////////////
const int maxn = 1e5+10;

char s[maxn];
int Next[maxn],pos[maxn],dp[maxn];

void getNext(){
    int len = strlen(s);
    Next[0] = 0, Next[1] = 0;
    for(int i=1; i<len; i++){
        int j = Next[i];
        while(j && s[i]!=s[j]) j = Next[j];
        Next[i+1] = (s[i]==s[j] ? j+1 : 0);
    }
}

int main(){
    cin >> s;
    getNext();
    for(int i=0; i<=strlen(s); i++)
        cout << i << " " << Next[i] << endl;
    int n = strlen(s);
    int cnt = 0;
    for(int i=Next[n]; i!=0; i=Next[i]){
        pos[cnt++] = i;
    }
    for(int i=0; i<=n; i++) dp[i] = 1;
    for(int i=n; i>=0; i--){
        dp[Next[i]] += dp[i];
    }
    cout << cnt+1 << endl;
    for(int i=cnt-1; i>=0; i--){
        cout << pos[i] << " " << dp[pos[i]] << endl;
    }
    cout << n << " " << 1 << endl;

    return 0;
}