题解 UVA10298 【Power Strings】

· · 题解

这里是对目前最高赞题解结论的证明。

结论：设字符串长度为n，最长相同前后缀的长度为next[i]，

如n%(n-next[n])=0，则答案为n/(n-next[n])，否则为1。

证明：

我们求next数组的时候，相当于每次把当前串这样对齐了一下↓

而next求到n时，上面串的n对应的就是下面串的next[n]。

这时候的n-nxt[n]就是箭头指向的绿色部分。

而上下两串其实是一样的，所以下面串的前n-nxt[n]格和上面串的前n-nxt[n]相同。

又因为两串由蓝色框住的部分匹配，所以下面的绿框对应的部分和绿框相同。

依此递推，可以得到，如果循环节多于一个，以前n-nxt[n]个为循环节，是可以铺满整串的。而且因为nxt[n]是尽量大的，所以这样得到的循环节长度为所有可能情况中最小的，也就是我们所求的。

而如果n%(n-next[n])≠0，可以认为之前的循环节匹配仍然可以进行，但是最后一个循环节被强行割掉了一些。

显然这样就怎么都安排不上了。

所以如n%(n-next[n])=0，就能排上，答案为n/(n-next[n])，否则只能以自己为循环节，答案为1。

代码实现的时候注意一下自己代码中n的定义和nxt数组的定义什么的。

还是放一下我的代码叭qwq

/*
    qwerta
    UVA10298 Power Strings
    Accepted
    代码 C++，0.65KB
    提交时间 2018-10-12 17:59:53
    耗时/内存
    100ms, 0KB
*/
#include<iostream>
#include<cstdio>
using namespace std;
int nxt[1000003];
int main()
{
    //freopen("a.in","r",stdin);
    while(1)
    {
        string s;
        getline(cin,s);//读入一整行，放进s
        if(s.length()==1&&s[0]=='.')break;
        int lens=s.length();
        //kmp求next
        int k=-1;
        nxt[0]=-1;
        for(register int i=1;i<lens;++i)
        {
            while(k!=-1&&s[i]!=s[k+1])k=nxt[k];
            if(s[i]==s[k+1])k++;
            nxt[i]=k;
        }
        int n=lens-1;
        if((n+1)%(n-nxt[n])==0)//如果能恰好排满循环节
        printf("%d\n",((n+1)/(n-nxt[n])));//输出总长除以循环节长度
        else printf("1\n");//否则输出1
    }
    return 0;
}

以上18.10.17

20.12.7更新：

关于讨论中提到的“可能有比(n-nxt[n])更长的目标子串”，可证该情况不存在，证明如下：

反证：如果存在，则有如图情况：

即左上方绿色段+橙色段=右下方黄色段+绿色段。

则推出左上方绿色段由黄色段开头，且两个绿色段相同。

推出右下方绿色段由黄色段开头...（这个递推和前文的递推类似

最后得出该目标子串由黄色小段重复而成，和题目要求的“最短字串”不符。

所以不存在比(n-nxt[n])更长的目标子串，原结论正确。

//没想到都大学了我还能看懂当年的题解，泪目