「UVA10298」 Power Strings（KMP

题目描述

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例#1：
复制

abcd

aaaa

ababab

.

输出样例#1： 复制

题解

Luogu的题解

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

结论：设字符串长度为$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[];

 int main()

 {

     //freopen("a.in","r",stdin);

     while()

     {

         string s;

         getline(cin,s);//读入一整行，放进s

         if(s.length()==&&s[]=='.')break;

         int lens=s.length();

         //kmp求next

         int k=-;

         nxt[]=-;

         for(register int i=;i<lens;++i)

         {

             while(k!=-&&s[i]!=s[k+])k=nxt[k];

             if(s[i]==s[k+])k++;

             nxt[i]=k;

         }

         int n=lens-;

         if((n+)%(n-nxt[n])==)//如果能恰好排满循环节

         printf("%d\n",((n+)/(n-nxt[n])));//输出总长除以循环节长度

         else printf("1\n");//否则输出1

     }

     return ;

 }

吐槽：拿来做模拟题压轴被吐槽是结论题......

明明前两天才讲过啊！（摔

巴特西

「UVA10298」 Power Strings（KMP

题目描述

输入输出格式

输入输出样例

题解

最新文章

热门文章