455 - Periodic Strings

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

favorites
New poster
Posts: 1
Joined: Thu Nov 22, 2012 5:14 pm

Re: 455 - Periodic Strings

Don't use gets(...), it would cause "Runtime error".
In this case, use scanf("%s",...); .

Alim14
New poster
Posts: 8
Joined: Sun Jan 05, 2014 3:40 pm

Re: 455 - Periodic Strings

I am getting continuously WA. Please help to find out the error of my code.

Code: Select all

/*
Algorithm: KMP
*/

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int lps;

void prefix_function(char *p)
{
int m=strlen(p+1);
lps=0;
int q=0;
for(int k=2;k<=m;k++)
{
while(q>0&&p[q+1]!=p[k])
q=lps[q];
if(p[q+1]==p[k]) q++;
lps[k]=q;
}
}

bool f(char *p)
{
int n=strlen(p+1);
for(int i=1;i<=n-1;i++)
{
if(p[i]!=p[i+1]) return 0;
}
return 1;
}

int main()
{
int i,j,k,d,t=0,n,test;
scanf("%d",&test);
char s;
while(test--)
{
scanf("%s",s+1);
prefix_function(s);
n=strlen(s+1);
//cout<<lps[n]<<endl;
if(f(s)) printf("1\n");
else if(n&1) printf("%d\n",n);
else if(lps[n]<n/2) printf("%d\n",n);
else
{
int jj=n-lps[n];
if(n%jj!=0) printf("%d\n",n);
else printf("%d\n",jj);
}
if(test) printf("\n");
}
return 0;
}
When I believe it is possible, I always find a way

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 455 - Periodic Strings

Try solving it using brute force.
Check input and AC output for thousands of problems on uDebug!

gaodechen
New poster
Posts: 1
Joined: Fri Aug 15, 2014 4:21 pm

455 - Periodic Strings

Hi, everyone!
I wrote 455 - Periodic Strings today, I submitted several times but always Wrong Answers... I don't know what's wrong with it, please give me a special vase, thanks!

Code: Select all

int main ( int argc, char *argv[] )
{
int t;
scanf( "%d", &t );

int len;
char s[SIZE];

int i, j, temp;
while( t-- )
{
scanf( "%s", s + 1 );
len = strlen( s + 1 );

for( i = 1; i <= len; i++ )
{
if( len % i != 0 )
continue ;

temp = 1;
for( j = i + 1; j <= len; j++ )
{
int m = ( j % i ) ? ( j % i ) : ( i );
if( s[j] != s[m] )
{
temp = 0;
break ;
}
}

if( temp )
{
printf( "%d", i );
break ;
}
}
if( t )
putchar( '\n' );
}

return EXIT_SUCCESS;
}				/* ----------  end of function main  ---------- */

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 455 - Periodic Strings

Next time post in the existing thread.

Post your full code with the #includes.
Check input and AC output for thousands of problems on uDebug!

yxszxwzh
New poster
Posts: 2
Joined: Sun Oct 05, 2014 4:34 am

455 - Periodic Strings，WA

Code: Select all

#include <cstdio>
#include<cstring>
#define MAXN 200
int main(){
char s[80+10];
int ok,p,n,len;
scanf("%d",&n);
while(n--){
scanf("%s",s);
len=strlen(s);
for(p=1;p<len;p++){
ok=1;
for(int i=p;i<len;i++){
if(s[i%p]!=s[i]) {ok=0;}
}
if(ok&&!(len%p))break;
}
if(n==0)printf("%d",p);
else printf("%d\n",p);
}
return 0;
}

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 455 - Periodic Strings，WA

Post in existing thread. Use search by problem number 455.
Two consecutive output are separated by a blank line.
Always print newline after last line and separate outputs by blank line. Change printing to

Code: Select all

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

if (n) puts("");
Don't forget to remove your code after getting accepted. A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

yxszxwzh
New poster
Posts: 2
Joined: Sun Oct 05, 2014 4:34 am

Re: 455 - Periodic Strings，WA

lighted wrote:Post in existing thread. Use search by problem number 455.
Two consecutive output are separated by a blank line.
Always print newline after last line and separate outputs by blank line. Change printing to

Code: Select all

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

if (n) puts("");
Don't forget to remove your code after getting accepted. Thanks.I don't pay attention to this sentence until you remind me.Now It's AC. wencey
New poster
Posts: 2
Joined: Fri Oct 31, 2014 6:08 pm

Re: 455 - Periodic Strings

Why my code get WA?
thank you.
C++11

Code: Select all

#include<iostream>
#include<vector>
#include<string>

using namespace std;
int main ( )
{
int a;
cin >> a;
for ( size_t __TIME = 1; __TIME <= a; __TIME++ )
{
string str;
cin >> str;
if ( str == "" )
{
__TIME--;
continue;
}
for ( size_t i = 1; i < str.length ( ); i++ )
{
if ( !( str.length ( ) % i ) )
{
string strt = str.substr ( 0 , i );
for ( size_t u = i; u < str.length ( ); u += i )
{
if ( strt == str.substr ( u , i ) )
{
if ( u + i == str.length ( ) )
{
if ( __TIME == a )
{
cout << i;

}
else
{
cout << i << endl << endl;

}
goto cd;
}
else
{
continue;
}
}
else
{
break;
}

}
}

}
if ( __TIME == a )
{
cout << str.length ( );

}
else
{
cout << str.length ( ) << endl << endl;

}
cd:;
}

return 0;

}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 455 - Periodic Strings

Print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

powerW
New poster
Posts: 1
Joined: Tue Jan 27, 2015 1:45 pm

Re: 455 - Periodic Strings

Getting WA, please help me Code: Select all

#include <stdio.h>
#include <string.h>
#define maxn 39999

int main()
{
int n;

char s, a, b;
freopen("J:\\oj.txt", "rb", stdin);

int count;
scanf("%d", &count);

int l, flag = 0;
for(l = 0; l < count; l++)
{
scanf("%s", s);
n = strlen(s);

int i;
for(i = 0; i < n; i++)
{
int j;
for(j = 0; j <= i; j++)
{
a[j] = s[j];
}
a[j] = '\0';
strcpy(b, a);

if(n%j == 0)
{
int m = n/j;
int k;
for(k = 1; k < m; k++)
{
strcat(a, b);
}

if(strcmp(a, s) == 0)
{
if(flag)
{
printf("\n");
}
printf("%d\n", i+1);
flag = 1;
break;
}
}
}
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 455 - Periodic Strings

Don't read from a file.
Check input and AC output for thousands of problems on uDebug!

yash_15
New poster
Posts: 1
Joined: Mon Sep 07, 2015 12:45 pm

Re: 455 - Periodic Strings Clarification

For all those struggling to get AC on this problem, note that you have to print a blank line in between two consecutive answers, but no blank line at the end of input.

Eg:
ans_1
--blank--
ans_2
--blank--
...
ans_t
| ( final location of cursor)

Peter0127
New poster
Posts: 1
Joined: Fri Nov 25, 2016 9:19 am

Re: 455 - Periodic Strings

I've try many possible string and got the right result. Could anybody help find if there is anything wrong?

Code: Select all

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

char buf;

int main(int argc, char const *argv[])
{
int Times;
scanf("%d", &Times);
while(Times--)
{
const int j = 0;
int T = 0;
memset(buf, ' ', sizeof(buf));
scanf("%s", buf);
int length = strlen(buf);
int first = 1;
for (int i = 1; i < strlen(buf); ++i)
{
if((i-1+T) > length) { break;} //end of looping

if (buf[i] == buf[j] &&first )
{
first = 0;
T = i - j;
for (int k = j; k < length-1-T; ++k)
{
if ( buf[k+T] != buf[k])
{
first = 1;
T = k + T;
break;
}
}
//break to here
}
}
if (first)
{
T = length;
}
printf("%d\n\n", T);

}
return 0;
}