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

Post by favorites » Thu Nov 22, 2012 5:40 pm

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
Location: BUBT,Dhaka, Bangladesh

Re: 455 - Periodic Strings

Post by Alim14 » Sat May 17, 2014 4:36 am

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

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

Re: 455 - Periodic Strings

Post by brianfry713 » Tue May 20, 2014 3:28 am

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

Post by gaodechen » Fri Aug 15, 2014 4:27 pm

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

Post by brianfry713 » Fri Aug 15, 2014 8:06 pm

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

Post by yxszxwzh » Sun Oct 05, 2014 4:38 am

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 by lighted » Sun Oct 05, 2014 9:24 am

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. 8)
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

Post by yxszxwzh » Sun Oct 05, 2014 3:32 pm

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. 8)
Thanks.I don't pay attention to this sentence until you remind me.Now It's AC. :D

wencey
New poster
Posts: 2
Joined: Fri Oct 31, 2014 6:08 pm

Re: 455 - Periodic Strings

Post by wencey » Tue Nov 04, 2014 7:07 am

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

Post by brianfry713 » Tue Nov 04, 2014 11:06 pm

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

Post by powerW » Tue Jan 27, 2015 1:51 pm

Getting WA, please help me :(

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;
}

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

Re: 455 - Periodic Strings

Post by brianfry713 » Tue Jan 27, 2015 9:26 pm

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

Post by yash_15 » Mon Sep 07, 2015 1:00 pm

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

Post by Peter0127 » Fri Nov 25, 2016 9:25 am

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;
}

Post Reply

Return to “Volume 4 (400-499)”