455 - Periodic Strings
Moderator: Board moderators
Re: 455 - Periodic Strings
Don't use gets(...), it would cause "Runtime error".
In this case, use scanf("%s",...); .
In this case, use scanf("%s",...); .
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[109];
void prefix_function(char *p)
{
int m=strlen(p+1);
lps[1]=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[109];
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
-
- 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!
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!
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 ---------- */
-
- 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.
Post your full code with the #includes.
Check input and AC output for thousands of problems on uDebug!
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;
}
Re: 455 - Periodic Strings,WA
Post in existing thread. Use search by problem number 455.
Don't forget to remove your code after getting accepted. ![8)](./images/smilies/icon_cool.gif)
Always print newline after last line and separate outputs by blank line. Change printing toTwo consecutive output are separated by a blank line.
Code: Select all
printf("%d\n",p);
if (n) puts("");
![8)](./images/smilies/icon_cool.gif)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
Re: 455 - Periodic Strings,WA
Thanks.I don't pay attention to this sentence until you remind me.Now It's AC.lighted wrote:Post in existing thread. Use search by problem number 455.Always print newline after last line and separate outputs by blank line. Change printing toTwo consecutive output are separated by a blank line.Don't forget to remove your code after getting accepted.Code: Select all
printf("%d\n",p); if (n) puts("");
![:D](./images/smilies/icon_biggrin.gif)
Re: 455 - Periodic Strings
Why my code get WA?
thank you.
C++11
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;
}
-
- 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!
Re: 455 - Periodic Strings
Getting WA, please help me
![:(](./images/smilies/icon_frown.gif)
Code: Select all
#include <stdio.h>
#include <string.h>
#define maxn 39999
int main()
{
int n;
char s[82], a[82], b[82];
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;
}
-
- 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!
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)
Eg:
ans_1
--blank--
ans_2
--blank--
...
ans_t
| ( final location of cursor)
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[90];
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;
}