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