lundi 29 mai 2017

UVA 455 Wrong answer... Please help... (passed the debug cases)

I did the UVA 455 Periodic Strings and passed the test cases in debug system but still got wrong answer... I tried some other cases and fixed a bug but still cannot pass...Please help..

This is the link for the question :http://ift.tt/2qugGFU

It is finding the repeating period for a string

eg:

if the input was ABC the period is 3

if the input was AAA the period is 1

if it was ABCABC, it is 3

ABBAAB it is 6

My method is brute force actually... I summed up different length of string and check whether they are equal, cause the characters are ints...

for ABAB A (index 0)!=B(index 1) (checking length 1)

then check (A(index 0)+B(index 1)) ?= (A(index 2)+B(index 3)) It is yes then answer is 2

for ABBA if the A(index 0) != B(index 2) when the checking length is 2 then it will break immediately

if(s[i]!=s[j]){
    equal = 0;
    break;
}

Here is the full code:

#include <iostream>
#include <string>
#include <cstring>
//#include <fstream>
#define maxn 85
using namespace std;

int main(){

    //ofstream myfile;
    //myfile.open("output.txt");
    int n;
    scanf("%d",&n);
    int equal;
    int len;
    while(n--){
        char s[maxn];
        scanf("%s",&s);
        int count = 1;
        len = strlen(s);

        for(count =1; count<= len/2;count++){
            equal = 1;
            int cur = 0;
            int a = 0, b = 0;
            while(cur+count < len){
                for(int i = cur,j=i+count;i<cur + count ||( j< (cur +2*count) && j<len);i++,j++){
                    if(s[i]!=s[j]){
                        equal = 0;
                        break;
                    }
                    a += s[i];
                    if(j<len) b += s[j];
                }
                cur+=count;
                if(a!=b){
                    equal = 0;
                    break;
                }else{
                    continue;
                }
            }
            if(equal == 1){
                //if(n-1>=0) myfile << count<<"\n\n";
                //else myfile << count<<"\n";
                if(n-1>=0) cout << count<<"\n\n";
                else cout << count<<"\n";
                break;
            }
        }
        if(equal == 0) //cout << len << "\n\n";
            //if(n-1>=0) myfile << len<<"\n\n";
            //else myfile << len<<"\n";
            if(n-1>=0) cout << len<<"\n\n";
            else cout << len<<"\n";
    }
    return 0;
}

Please help...thank you so much!

Aucun commentaire:

Enregistrer un commentaire