yeah, figured out that part, intersection of all possible n is to be used. But everything done, my code now dies in TLE.I figure I am having O(n^2) complexity. Please help me out, by directing me to some better approach. Is there any DP approach or did I miss some crucial optimization step? Please help
int main(){
int no,n,i,j,kbase,kval,top,N,misVal,counter;
char tmp;
bool flag;
cin>>no;
while(no>0){
no--;
string x,y;
cin>>N;//Max length of cypher
cin>>x;//Plain text
cin>>y;//Encrypted text
int kMap[x.length()][2];
int mismatch[N+1];//As 0 is left unconsidered
//Initializing the array containing the values of n that is never possible
for(i=0;i<=N;i++)
mismatch[i]=-1;
top = -1;
for(i=0;i<x.length();i++){
//If both the values are known, we can determine the k values
if((x[i]!='*')&&(y[i]!='*')){
kval=(y[i]+26-x[i])%26;
//Chekcing for possible mismatch
for(j=top;j>=0;j--){
//Mismatch occurs
if(kMap[j][1]!=kval){
misVal=i-kMap[j][0];
mismatch[misVal]=1;
}
}
top++;
//Insert the k value and the index in the k-map
kMap[top][0]=i;
kMap[top][1]=kval;
}
}
//If a n is not possible, so is all its factors also, calculating those values
for(i=0;i<=N;i++){
if(mismatch[i]==1)
storeMisVal(misVal,N,mismatch);
}
n=-1;
char mem[x.length()];
int k[N];//Array holding cyphers.
counter=-1;
//Initialzing array to hold the plaintext
for(i=0;i<x.length();i++)
mem[i]=1;
//Detecting the value of n
for(i=N;i>0;i--){
if(mismatch[i]==-1){
n=i;
}else
continue;
counter++;
//Initializing the values of k.
for(j=0;j<N;j++)
k[j]=-1;
for(j=0;j<=top;j++){
kbase=kMap[j][0];
kbase%=n;
k[kbase]=kMap[j][1];
}
for(j=0;j<x.length();j++){
//The text is inelligible to compute, meaning for different n, the value is not unique.
if(mem[j]==0)
continue;
//If encrypted text is inelligible or plaintext is elligible,then print the plaintext as it is.
if((y[j]=='*')||(x[j]!='*')){
if(counter==0)
mem[j]=x[j];
else if(mem[j]!=x[j]){
mem[j]=0;
}
continue;
}
kbase=j%n;
if(k[kbase]==-1){
if(counter==0)
mem[j]=x[j];
else if(mem[j]!=x[j]){
mem[j]=0;
}
continue;
}
tmp=y[j]-k[kbase];
if(tmp<65){
if(counter==0)
mem[j]=(char)(tmp+26);
else if(mem[j]!=(char)(tmp+26)){
mem[j]=0;
}
}
else{
if(counter==0)
mem[j]=tmp;
else if(mem[j]!=tmp){
mem[j]=0;
}
}
}
}
//Print the generated plaintext, for those values with conflicting for different n, original plaintext letter is used.
for(i=0;i<x.length();i++){
if(mem[i]!=0)
cout<<mem[i];
else
cout<<x[i];
}
cout<<endl;
}
}
//Function to store the value and all their factors as well in the mismatch array.
int storeMisVal(int val,int max,int mismatch[]){
int i;
if(val<=max)
mismatch[val]=1;
for(i=val-1;i>0;i--){
if(val%i==0){
if(mismatch[i]!=1)
storeMisVal(i,max,mismatch);
}
}
}