UVa455 Periodic String 的wronganswer问题探讨，以及AC的新思路

题目的意思是一个字符串有某个长度为k的字符串通过不断重复形成的，而k被称为该字符串的周期。而我们所要做的是找出该字符串的最小周期。

input

The first line is an integer T,That means there are have T test cases; the following T lines are T strings;

output

Each line is an answer,and there a blank line between two answers.

（具体的题目描述请参考原题）

分析：在开始看到这个题目的时候，第一个想到的是从第一个字符开始找，开始假设最小周期min=1;只要对string进行一次遍历，并且在遍历的过程中，以min的间隔分别和字符串开头的min个字符进行比较，如果出现不相同，比如恰巧遍历到j位置，那么min就转化为j+1;启发源于：abcabcabcadcab,在d位置出现了不同，那么min=11;于是便得出了下面的代码：

#include<stdio.h>
#include<string.h>
int main()
{
int T;
char s[81];
int min,t,j,flag;
scanf("%d",&T);
//printf("\n");
for(int i=0;i<T;i++)
{
scanf("%s",s);
int l = strlen(s);
min=1;
for(j=1;j<l;j++)
{

t=j;

for(int k=0;k<min;k++)
{
if(t+k<l)
{

j=t+k;
if(s[k]!=s[j])
{
flag=0;
break;
}
}
}
t=t+min;
if(flag==0)
{
break;
}
}
if(flag==1)
{
break;
}

if(min>l/2)
{
min=l;
break;
}
}
}
if(i==T-1)
printf("%d\n",min);
else
printf("%d\n\n",min);
}
return 0;
}

在一开始，觉得这个思路应该是比较正确的，不会有什么不妥，然而提交的结果是Wronganswer,尽管后期对细节进行了处理，比如周期超过l/2则周期为l;但是都没有通过。

因为wweewwwweeww,这个字符串用上面的思路是绝对行不通的。因此可以肯定上面的wronganswer是思路上错了。

那么可以确保正确的思路又是怎么样的呢？

1.比较明显的特点，周期min必定是strlen(s)的因子，而且是最小的，因此利用一个循环从小到大对strlen(s)的因子进行判定是否符合条件即可，其中需要花些心思的是如何进行判定周期是符合条件的。其实，只要将之后的每一段和第一段进行比较或者在之后的每一段的每个字符进行比较，第一个循环为每个字符的循环，嵌套一个是否相等的循环，用一个flag进行标记，方便外循环的break，因为只要有内循环出现不相等，则外循环之后都不需要进行比较了。

代码应该表较容易写出来。

2.是在第一种思路上和错误的思路相结合的方式。每个循环，其第一个字符必定和s[0]，是相等的，因此只要再加上s[j]==s[0]&&l%j==0可以个快速的进行判定。

具体代码如下：

while(t<=l-min)
{
flag=1;
for(int k=0;k<min;k++)
{
if(t+k<l)
{
if(s[k]!=s[t+k])
{
flag=0;
break;
}
}
}
t=t+min;
if(flag==0)
{
break;
}
}
if(flag==1)
{
break;
}

if(min>l/2)
{
min=l;
break;
}
}
}
if(j>=l)
{
min=l;
}
if(i==T-1)
printf("%d\n",min);
else
printf("%d\n\n",min);
}
return 0;
}

最后，只得一说的是原题在INPUT的内容里加上了T...followed by a blank line，其实并没有起到任何作用，别管就是。在输出时也要注意下输出格式题目就可以解决了。

巴特西

UVa455 Periodic String 的wronganswer问题探讨，以及AC的新思路

最新文章

热门文章