alohamaloha's blog

By alohamaloha, 12 years ago, In English
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<stack>
#include<queue>
#include<string>
#include<cstring>


#define PR(x) printf("")
#define READ2(x,y) scanf("%d %d",&x,&y)
#define REP(i,a) for(int i=0;i<a;i++)
#define READ(x) scanf("%d",&x)
#define PRARR(x,n) for(int i=0;i<n;i++)printf("")
using namespace std;
typedef long long ll;
int main() { 
string s1,s2;
cin>>s1;cin>>s2;
int idx=1;
string subst;
char ch=s1[0];
int len1=s1.length();
int len2=s2.length();
int lenC=1;
while(idx<len1&&ch!=s1[idx++]) lenC++;
PR(lenC);
if(lenC!=len1) {

for(int j=1;j<lenC&&j<len1;j++){
while(len1%lenC!=0) lenC++;
for(int k=j+lenC;k<len1;k+=lenC){
if(s1[j]!=s1[k]) {
//printf("VIolation at %d %d char values %c %c\n",j,k,s1[j],s1[k]);
k-=lenC;
lenC+=1;

}

}
}

}
lenC=min(len1,lenC);
int count1=0;
for(int i=1;i*lenC<=len1;i++) count1++;
PR(lenC);
PR(count1);
subst=s1.substr(0,lenC);
if(len2%lenC!=0||len2<lenC) {
			puts("0");
			return 0;
		}
bool flg=false;
for(int i=0;i<lenC;i++){
for(int j=i;j<len2;j+=lenC)
if(s2[j]!=subst[i]){
//printf("VIolation at %d %d char values %c %c\n",i,j,s2[j],subst[i]);
flg=true;
break;
}
if(flg) break;
}
if(flg) {
		puts("0");
		return 0;
	}
int num2=0;
for(int i=1;i*lenC<=len2||i*lenC<=len1;i++) if(len2%(i*lenC)==0&&len1%(i*lenC)==0)num2++;
int ans=num2;
printf("%d\n",ans);
}

I am getting wrong answer on pretest 9.The pretest is very long so can't see the complete test case. My solution is based on the following approach 1.if a substring x is a divisor of a string S then it will be either a.Shortest divisor of S(in terms of length) b.It can be broken down into smaller divisors based on the constraint for all divisor length l S.length()%l==0

I find out the smallest divisor in either string,then check if it is a divisor in the other string,if it is not then the strings dont have any common divisor.In case it is a divisor then i combine the smaller divisor to get bigger divisors such that the length of bigger divisors divide both S1.length() and S2.length() where S1 and S2 are the input strings.

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
12 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

In that case the pattern of the test case gives you enough insight to find the issue. Try a simpler test case: aabb aabb.

Your initial lenC will be 1 since the first two characters match. But you never enter the for loop (1 < lenC is not true).

A general remark for future posts: If you want people to provide comments you need to provide readable code which means that you should use the correct formatting (block indents, etc.) and also add comments if possible (e.g. what variables stand for).

  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanx cholerikasi I will keep that in mind..

    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Got AC simply by changing the loop from j=1 to j=0...Reason still why i am a pupil :( Thanx once again cholerikasi I posted this on the blog because I was sure I had the right algorithm.Feeling like a floppy disk now.:(