455 - Periodic Strings

[Nick]

[nrkt]

I can't get what's wrong with this code:

[java]
import java.io.*;

class Main {

static String read() {
int maxLg = 255;
byte lin[] = new byte[maxLg];
int lg = 0, car = -1;
String line = "";
try {
while (lg < maxLg) {
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
if (car != 13)
lin [lg++] += car;
}
}
catch (IOException e) {
return (null);
}
if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

static int smallestPeriod(String input) {
for (int i = 1; i<= input.length(); i++) {
String temp = input.substring(0,i);
String ris = "";
int x = temp.length();
while (ris.length() < input.length()) ris += temp;
if (ris.equals(input)) return x;
}
return 0;
}

static void main(String[] args) {
int multinput = Integer.parseInt(read());
for (int i=0; i<multinput; i++) {
String input = read();
System.out.println(smallestPeriod(input));
}
}
}
[/java]

According to the Online Judge, it does not solve problem 455.
Could anybody help me plz? Thanx a lot

[the LA-Z-BOy]

shouldn't the main() method be public?
moreover this is a multiple input problem... you're not handling it accordingly. the input is formed something like this..

Code: Select all

3

Hello

HoHoHo

ByeByeByeNot

so you have to track blank lines at each input block...
[java] public static void main(String[] args) {
int multinput = Integer.parseInt(read());
for (int i=0; i<multinput; i++) {
String dummy = read(); // take the blank line
String input = read();
System.out.println(smallestPeriod(input));
}
}[/java]
Greetings

[nrkt]

thanx a lot LA-Z-BOy, I corrected it the way you suggested and it ran ok

[Bug!]

Hi all .
I've read all the previous topic about this one, and i've tried all the given input, n the output is correct. But I still got WA for this problem. I've got WA for about 6 times. Hope I can get another sample input

input:

Code: Select all

5

HoHoHo
dodoldudulzz
mangomangomangom
dodod

abcabcabcabc

HoHaHo

ooHooH

abaaababaaab

output:

Code: Select all

2
12
16
5

3

6

3

6

Is it correct??

Thanx, regard
Andre

[Bug!]

And This is my code

Code: Select all

got ac now

[rezwana]

is the way of taking multiple input correct?

But when i run my program it stops execution after one "end of file"
input.

Anyway my code shows correct answers for

abaaababaaab
6
mangomangomangom
16
ababc
5
hohoho
2
ababcababc
5
asdfgh
6


i think the prob is in the way of taking multiple input

plz HELP

my code is here


#include<stdio.h>
#include<string.h>

char str[100],temp[100];
int p,pr,prlen,index;
int fstrcmp(){
int j,k;
pr=0;
index=p+strlen(temp);
for(j=0,k=p;temp[j];j++,k++)
if((temp[j]-str[k])!=0)
{ pr=1;
index=k;
break;}
return pr;
}

int main(){
int i,len,flag=0,t,m;
char ch;
scanf("%d",&t);
for(m=0;m<t;){
while(NULL!=gets(str)){
temp[0]='\0';
flag=0;
len=strlen(str);
prlen=len;

ch=str[0];
i=1;
while(str){
if(str==ch)
{ flag=0;
p=i;
strncpy(temp,str,i);
temp='\0';
if(len%p==0)
{
if(fstrcmp()==0)
{
for(p=2*i;p<len;p=p+i)
if(fstrcmp()!=0)
{ flag=1;
break;}
if(flag==0)
{prlen=i;
break;}
else
i=index+1;
}
else
i++;
}
else
i++;
}
else
i++;
}
printf("%d\n",prlen);
}
m++;
}
return 0;
}

[sidky]

It seems to me that, you didn't handle multiple input properly. There are blank lines between the cases, and for those strings, your program will produce 0 as output.

[rezwana]

hi,

i know there is prob in taking multiple input.
i want to know the solution.

CAN ANYONE HELP ME PLZ.

[oulongbin]

[cpp]
#include <iostream>
using namespace std;
#include <cstring>
int main()
{
int n,l,j,i,count,m;
char a[1000];
cin>>n;
cin.get();
for(int sum=0;sum<n;)
{
cin.getline(a,1000);
if(a[0]=='\0')
{sum++;cout<<endl;}
else
{
l=strlen(a);

if(l%2==0)
{
count=0;
for(i=2;i<=l;i++)
{
if(l%i==0)
{
for(j=0;j<l/i;j++)
{
if(a[j]==a[j+l/i]){}
else break;
}
if(j==l/i)
{
for(m=1;m<i;m++)
{
if(a[0]==a[m*j]){}
else
break;
}
if(m==i)
count=j;
}

}
}
if(count==0)
count=l;
cout<<count<<endl;
}

else
{
count=0;
for(i=1;i<l;i+=2)
{
if(i==1)
count=l;
else
{
if(l%i==0)
{
for(j=0;j<l/i;j++)
{
if(a[j]==a[j+l/i]){}
else
break;
}
if(j==l/i)
count=j;
else
break;
}
}
}
for(i=1;i<strlen(a);i++)
{
if(a==a[0]){}
else break;
}
if(i==strlen(a))
count=1;

cout<<count<<endl;
}
}
}
return 0;
}
[/cpp]

i do not know why i always geo WA.i think its right.
please help me.
thank you !

[Sedefcho]

Hello, I need some sample I/O

Here is some sample Input and the Output from my WA program.

Code: Select all

10 

abaaababaaab

ooHooH

abaaababaaab 

b  aab  aa

ababc 

hohoho 

ababcababc 

asdfgh

rrr rrr zzz rrr rrr zzz

HoHaHo

Output

Code: Select all

6

3

13

5

6

7

11

6

23

6

I tried also not to print blank lines between consecutive OUTPUTs
but that also resulted in WA. Any help will be highly appreciated.

Thanks in advance.

[mf]

The output of my accepted program is quite different from yours:

Code: Select all

6

3

6

5

5

2

5

6

23

6

Maybe you have some problems with reading input, or misunderstood the problem. Shouldn't it be obvious that for "hohoho" the answer is 2? This example modulo case is given in the sample input/output.

[Sedefcho]

Hi, mf!

Firstly thanks for looking into my problem.

Note that I've had one trailing space on each line of
my sample input. That's why I was getting these
strange results. Sorry for posting them !

Now for the same input ( without any trailing spaces )
I get the following output

Code: Select all

6

3

6

5

5

2

5

6

23

6

As you can see it is absolutely the same as yours. Why do I get WA
then. Currently I have no idea.
Do you have any idea ?

Some tricky input ?

By the way for this problem my program is in Java so I doubt
that I read the input in a wrong way, I've done it a lot
of times.

One question: Can we assume the line which comes from
the stdin has no leading or trailing blanks ( blanks are not
only SPACEs but also TABs for instance ).

I have no idea, can we have such input ?!

Can we also an input in which our input line is just empty.
I mean something like:

Code: Select all

line1
empty line 
empty line 
empty line
line3

And more thing - is 80 really the maximum
length of the input lines ?

If you also have no idea of what is wrong can you just give
me some more test cases. I hope some of them could reveal some
BUG program has.

[Sedefcho]

I've found my BUG. It was very stupid one.

I have a precheck where I test if my string is such that
it's period is 1. So I test if the string contains only one symbol.

But I was forgetting its last symbol ( just a stupid
typing mistake which made my program miss the last
symbol of the string ).

So for inputs like AB, AAB, AAAB my program was giving
an answer of 1 although the correct answer is N where N is the
length of the string ( AB -> 2, AAB -> 3, AAAB -> 4 ).

The reason we did not manage to notice this before, is that there
were no such cases in the test input I've posted above. I mean cases
where all symbols are equal and just the last one is different.

Pretty stupid, I know. To mf : thanks once again.

[Wei-Ming Chen]

Ac now, thanks everyone's help.