455 - Periodic Strings

[chunyi81]

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

But your code gives:

Code: Select all

2

3

2

100

edited: Input format was wrong. Now it's corrected. There are some test cases from past threads.

[Wei-Ming Chen]

But the problem said:
"Two consecutive input will separated by a blank line."

[chunyi81]

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

But your code prints:

Code: Select all

6

3

6

5

5

2

5

6

23

100

[Wei-Ming Chen]

I changed my code, so it could said "6" in last ouput
But still got WA.......

[temper_3243]

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]

hmm...
I solved it first time with O(n^3).
After that i solved it with O(n^2). So try to think about this ORDER.

hope this will help you more.

[algoJo]

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

[Jan]

Try the following case

Input:

Code: Select all

1

ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ

Output:

Code: Select all

1

Hope it helps.

[algoJo]

Thanks for ur reply Jan
finally AC

[Jan]

You should remove the faulty I/O set, too. The output should be 1.

[Amin.Abouee]

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]

Search the board first. Don't open a new thread if there is one already.

[yesacm91]

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]

Use an existing thread.

[Obaida]

It seems i must have the wA.
I tested all the cases but still WA. please help me.

Code: Select all

removed