## 455 - Periodic Strings

Moderator: Board moderators

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

nrkt
New poster
Posts: 2
Joined: Sat Jul 19, 2003 2:30 pm
Contact:

### Problem 455: WA

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

[java]
import java.io.*;

class Main {

int maxLg = 255;
byte lin[] = new byte[maxLg];
int lg = 0, car = -1;
String line = "";
try {
while (lg < maxLg) {
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) {
for (int i=0; i<multinput; i++) {
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
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
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) {
for (int i=0; i<multinput; i++) {
String dummy = read(); // take the blank line
System.out.println(smallestPeriod(input));
}
}[/java]
Greetings Istiaque Ahmed [the LA-Z-BOy]

nrkt
New poster
Posts: 2
Joined: Sat Jul 19, 2003 2:30 pm
Contact:
thanx a lot LA-Z-BOy, I corrected it the way you suggested and it ran ok

Bug!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am

### 455, need some sample input

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!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am
And This is my code

Code: Select all

``````got ac now
``````

rezwana
New poster
Posts: 3
Joined: Wed Feb 18, 2004 7:30 am

### why WA 455

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,temp;
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';
flag=0;
len=strlen(str);
prlen=len;

ch=str;
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
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
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
New poster
Posts: 3
Joined: Wed Feb 18, 2004 7:30 am

### WHY wa 455

hi,

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

CAN ANYONE HELP ME PLZ.

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

[cpp]
#include <iostream>
using namespace std;
#include <cstring>
int main()
{
int n,l,j,i,count,m;
char a;
cin>>n;
cin.get();
for(int sum=0;sum<n;)
{
cin.getline(a,1000);
if(a=='\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==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){}
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.
thank you !

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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.
Last edited by Sedefcho on Fri Apr 29, 2005 1:18 am, edited 1 time in total.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
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
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan