[codeforces/gym/100431/E]KMP关于border的理解

题目链接：http://codeforces.com/gym/100431/

考虑到对于一个串β，能cover它的最短的α必然是它的border的某个前缀，或者是这个β本身。

所谓border，就是next[len(β)]，直观含义是除了串本身以外，使得前缀等于后缀的最长的一段前缀。

发现如果border的两倍就能覆盖整个串，那么问题的规模就减半了，只要求出能cover这个border的最短的串即可。这个关系是具有传递性的，只要border够长，就一直可以推下去。而这种关系可以通过一个last数组实现路径压缩。

如果border的两倍不能覆盖整个串，那就要看border的哪一个前缀可以了，那么哪些前缀可以呢？只有哪些border的border才有可能可以。这是为什么呢？因为只有哪些border的border，才是β串的公共前后缀。那么我们通过一个far数组，维护每一个前缀最远能够覆盖到的位置，动态维护这个数组，通过last数组路径压缩加速即可。

要注意的是far数组的更新要一路更新到底，否则无法把信息维护全。

#include<bits/stdc++.h>

using namespace std;

void kmp_pre(char x[],int m,int nxt[])

{

    int i,j;

    j=nxt[]=-;

    i=;

    while(i<m)

    {

        while(-!=j && x[i]!=x[j])j=nxt[j];

        nxt[++i]=++j;

    }

}

const int maxn=;

char s[maxn];

int nxt[maxn];

int last[maxn];

int far[maxn];

int main()

{

    freopen("cover.in","r",stdin);

    freopen("cover.out","w",stdout);

    scanf("%s",s);

    int l=strlen(s);

    kmp_pre(s,l,nxt);

    for (int i=;i<=l;i++) if (nxt[i]*>=i) last[i]=last[nxt[i]]; else last[i]=i;

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

    {

        int j=last[i];

        far[j]=i;

        int now=i;

        while (j)

        {

            if (far[j]>=i-j)

            {

                now=j;

                far[now]=i;

            }

            j=last[nxt[j]];

        }

        printf("%d ",now);

    }

    return ;

}