## 455 - Periodic Strings

Moderator: Board moderators

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
Try the following test case:

Code: Select all

``````4

HoHoHo

abcabc

HoHoHo

the cat ran out
``````
Correct output is:

Code: Select all

``````2

3

2

15
``````

Code: Select all

``````2

3

2

100
``````
edited: Input format was wrong. Now it's corrected. There are some test cases from past threads.
Last edited by chunyi81 on Mon Jan 23, 2006 8:05 am, edited 2 times in total.
Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
But the problem said:
"Two consecutive input will separated by a blank line."
chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
Sorry about that. I have corrected the test case. Check the new test case I have posted. Your code gives wrong output.

Test case from a past thread:

Code: Select all

``````10

abaaababaaab

ooHooH

abaaababaaab

b  aab  aa

ababc

hohoho

ababcababc

asdfgh

rrr rrr zzz rrr rrr zzz

HoHaHo
``````
Correct output is:

Code: Select all

``````6

3

6

5

5

2

5

6

23

6
``````

Code: Select all

``````6

3

6

5

5

2

5

6

23

100
``````
Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan
I changed my code, so it could said "6" in last ouput
But still got WA.......
temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

### 455 brute force

Hi,
I have a problem. I have got it accepted for 455 with the below algorithm.

for (len=1 ; len < stringlen ;len++)
check(string,len);

check function checks if string has a period of len.

This algorithm has o(n^3) because check has o(n^2) (one for loop and one strcmp inside the for loop), this is really brute force and i don't think i have accomplished anything by solving this problem . I want to do it for strings of length 1000 and if possible 10^6.

How can we find the smallest period of a string in better time. Can someone point to me better algorithm and links.

Thanks
Nik
DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
hmm...
I solved it first time with O(n^3).

algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am
I've checked my program with inputs from this board and it gave the correct outputs but it continue to WA...
can anybody give me some hint...

Code: Select all

``````Removed
``````
and is it right if
INPUT

Code: Select all

``````1

aaaaaaaaaaaa
``````
OUTPUT

Code: Select all

``````1
``````
Last edited by algoJo on Mon Jan 22, 2007 12:09 am, edited 2 times in total.
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Try the following case

Input:

Code: Select all

``````1

ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ``````
Output:

Code: Select all

``1``
Hope it helps.
Ami ekhono shopno dekhi...
HomePage
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am
finally AC
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
You should remove the faulty I/O set, too. The output should be 1.
Ami ekhono shopno dekhi...
HomePage
Amin.Abouee
New poster
Posts: 1
Joined: Fri May 18, 2007 11:37 am

### 455 Why PE

My output is correct But my output format is wrong

#include <iostream>
#include <string>
using namespace std;

int main()
{
string sta="";
string temp="";
string test="";
size_t equal=0;
size_t size_temp=0;
size_t size_sta=0;
bool status;
int T;
int pass=0;
cin>>T;
getline(cin,sta);
cout<<endl;
while (getline(cin,sta))
{
if(sta=="")
{
cout<<endl;
pass++;
continue;
}
status =false;
size_sta=sta.length();
for (size_t i=1;i<size_sta && status==false;i++)
{
if (sta==sta[0])
{
temp=sta.substr(0,i);
size_temp=temp.length();
if (size_sta%size_temp!=0)
continue;
else
{
equal=size_sta/size_temp;
for (size_t j=1;j<equal;j++)
{
size_t p=(i*j);
test=sta.substr(p,i);
if (test==temp)
{
status=true;
continue;
}
else
{
status =false;
break;
}
}
}
}
}
if (status==true)
cout<<size_temp;
else
cout<<size_sta;
if (pass!=T)
cout<<endl;
}
return 0;
}
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage
yesacm91
New poster
Posts: 1
Joined: Fri Mar 07, 2008 2:09 pm

### 455 - you can use this kind of IO format (Accepted)

After tring several times in the IO test, I find that we don't have to deal with the following situation

Code: Select all

``````1

a  ba  b
``````
For those who do not know the IO format, you can try the format below.

Code: Select all

``````#include<stdio.h>
/*455*/
int main(){
int n, period;
char str[200];
/*write what you want*/

scanf("%d", &n);

while(n--){
scanf("%s", str);

/*write what you want..*/

printf("%d\n", period);

if(n > 0) /*<--important*/
printf("\n");
}

return 0;
}``````
Best Regards,
yesa
Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Re: Help with 455

It seems i must have the wA.

Code: Select all

``removed``
Last edited by Obaida on Thu Jan 22, 2009 11:24 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.