strings prefix isomorphism with max length

Question

string s1 and s2 are isomorphic means—— if we make the two string into rings,the two rings are the same. Example:"abcd" and "cdab" are isomorphic ”abcd“ and "dcba" are not isomrphic "cdab" and "abdc" are not too.

Now you have two strings, output a max length make the prefixs of the two strings with the length isomorphic.

Example:"abcdx" and "cdabz" the max length is 4.

Time complexity as low as possible.

PS: The length of the two strings are the same

Here is a wrong solution,but passed all test

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <stack>
#include <string>
#include <algorithm>
#define MAXN 2000001
#define MOD 100000007
using namespace std;
char str1[MAXN],str2[MAXN];
int next1[MAXN],next2[MAXN],n;
int p[27][26],ct=0;
void getnext(char *s1,char *s2,int* next){
    next[0]=0;
    int pos=2,cnd=0;
    while(pos<n){
        if(s1[pos-1]==s2[cnd])
        {++cnd;next[pos]=cnd;++pos;}
        else if(cnd>0)cnd=next[cnd];
        else {next[pos]=0;++pos;} 
    }
}
void getpri(){
    int cnt=0;
    for(int i=2;cnt<26;i++){
        bool flag=true;
        for(int j=2;j*j<=i;j++)if(i%j==0){flag=false;break;}
        if(flag)p[cnt][ct++]=i;
        if(ct==26)++cnt,ct=0;
    }
}
string s1,s2,str;
bool check(int p){
    str=string(s1.substr(0,p)+s1.substr(0,p));
    int res=str.find(s2.substr(0,p));
    if(res!=-1)return true;
    return false;
}
stack<int>stk;
int main()
{
    freopen("beyond.in","r",stdin);
    freopen("beyond.out","w",stdout);
    getpri();
    scanf("%d\n%s\n%s",&n,str1,str2);
    s1=str1;s2=str2;
    getnext(str1,str2,next1);
    getnext(str2,str1,next2);
    int ans=0;
    long long h1=1,h2=1;
    for(int i=0;i<n;i++){
        if(i>0){
            h1=(h1*p[str1[i-1]-'a'][str1[i]-'a'])%MOD;
            h2=(h2*p[str2[i-1]-'a'][str2[i]-'a'])%MOD;
        }
        if(next1[i+1]+next2[i+1]>=i&&
        h1*p[str1[i]-'a'][str1[0]-'a']==
        h2*p[str2[i]-'a'][str2[0]-'a'])stk.push(i+1);
    }
    while(!stk.empty()){
        if(check(stk.top())){ans=stk.top();break;}
        stk.pop();
    }
    printf("%d\n",ans);
    return 0;
}

PS:There may be no O(n) solution to this problem , O(n) solution exists only when one of the strings is its the minimum representation.

Answer 1

I thought a lot on this problem and what i got is that this problem is simpler than we thought. According to me you can solve this by keeping links (a,b) which suggests character a precedes b in a circular permutation. If the all links of string1 and string2 are same then it means they are the same circular permutation. The trick here is to give a link (a,b) +1 value for string1 and -1 for string2 hence if all links are same then all pairs (a,b) will have zero count. This can be achieved using pair count arr[26][26] for all alphabet pairs where arr[a][b] represents number of net links (a,b) are there in difference of the two permutations.

Proof that circular permutation can fully be represented by set of links :-

Consider a circular permutation :-

x0->x1->x2->x3->x0

representation in set of links :- (x0,x1),(x1,x2),(x2,x3),(x3,x0)

The claim is that this set of links always represents the above permutation only.

We will prove this by contradiction. Lets assume that there is a different circular permutation that can be represented by same set of links. Then there can be different circular permutation that be formed by swapping two characters.

We swap x1 and x3 then we get permutation:-

x0->x3->x2->x1->x0

**set of links :-** (x0,x3),(x3,x2),(x2,x1),(x1,x0)

There are two possibilities :-

1. x1 == x3 then new permutation is same as old so there is contradiction here.
2. x1 != x3 then (x0,x3) != (x0,x1) , (x3,x0) != (x1,x0) hence again there is contradiction.


This result can be extended to multiple swaps.

Hence it is proved by contradiction that set of links represent only one circular permutation.

Using this result i have written the following c++ implementation :-

#include<cstdio>
#include<cstring>

inline int getval(char ch) {

 return ch-'a'; 
}



int isomorphic_prefix(char* str1,char* str2) {

 int edges[26][26] = {0};
 int n = strlen(str1);
 int isoprefix = 0;
 int simedges = 676;
 int first1 = getval(str1[0]);
 int first2 = getval(str2[0]);

 for(int i=0;i<n;i++) {


    int prev1,prev2;
    if(i>0) {
        prev1 = getval(str1[i-1]);
        prev2 = getval(str2[i-1]);
    }


    int curr1 = getval(str1[i]);
    int curr2 = getval(str2[i]);

    if(i > 0) {
        if(edges[prev1][first1] == 1)
            simedges++;
        else if(edges[prev1][first1] == 0)
            simedges--;
        edges[prev1][first1]--;
        if(edges[prev2][first2] == -1)
            simedges++;
        else if(edges[prev2][first2] == 0)
            simedges--;
        edges[prev2][first2]++;
        if(edges[prev1][curr1] == 0)
            simedges--;
        else if(edges[prev1][curr1] == -1)
            simedges++;
        edges[prev1][curr1]++;
        if(edges[prev2][curr2] == 0)
            simedges--;
        else if(edges[prev2][curr2] == 1)
            simedges++;
        edges[prev2][curr2]--;

    }

    if(edges[curr1][first1]==0)
        simedges--;
    else if(edges[curr1][first1] == -1)
            simedges++;
    edges[curr1][first1]++;

    if(edges[curr2][first2]==0)
        simedges--;
    else if(edges[curr2][first2] == 1)
            simedges++;
    edges[curr2][first2]--;

    if(simedges == 676)
        isoprefix = i+1;
 }

 return isoprefix;

}




int main() {
    char str1[100];
    char str2[100];
    gets(str1);
    gets(str2);
    printf("%d",isomorphic_prefix(str1,str2));
    return 0;   
}

Time Complexity :-

As you can see in the implementation it is a single loop of O(N) with constant calculations inside hence it is O(N).

Answer 2

I think you can solve this using following method :-

1. Find longest prefix for each substring string1[0 to i] which are also suffix for substring string2[0 to i] and visa versa.Lets call them lps1[i] & lps2[i].
2. if lps1[i] + lps2[i] == i+1 then prefix upto i is isomorphic

example :-

string1 = "abcdx" 
string2 = "cdabz"

lps1[0] = 0
lps2[0] = 0

lps1[1] = 0
lps2[1] = 0

lps1[2] = 1
lps2[2] = 1

lps1[3] = 2
lps2[3] = 2

lps1[4] = 0
lps2[4] = 0

lps1[3] + lps2[3] = 4 = 3+1 hence the largest prefix isomorphic is of length 3+1 = 4

Now main question is how to find lps efficiently ?

KMP uses a similar algorithm to build a table in O(|S|). Check the part table-building algorithm it basically constructs lps for string with itself but you can replace

if W[pos - 1] = W[cnd] 

by:-

if string1[ pos-1 ] = string2[cnd]  

with some corner checks like cnd < string2.length

Time complexity :-

Build LPS arrays : O(|S1|+|S2|)

check isomorphic prefix : O(min(|S1|,|S2|)

Here is c++ implementation :-

#include<cstdio>
#include<cstring>



void ComputeLPS(char* str1,char* str2,int n,int LPS[]) {
  LPS[0] = 0;
  int len = 0,i=1;
  while(i<n){
    if(str2[len]==str1[i]) {
      len++;
      LPS[i] = len;
      i++;
    }
    else {

      if(len!=0) {
    len = LPS[len-1];
      }
      else {
    LPS[i] = 0;
    i++;
      }
    }

  }



}


int isomorphic_prefix(char* str1,char* str2) {

  int n = strlen(str1);
  int lps1[n];
  int lps2[n];

  ComputeLPS(str1,str2,n,lps1);
  ComputeLPS(str2,str1,n,lps2);
  int max = 0;

  for(int i = 0;i < n;i++) {

    int k = lps1[i]+lps2[i];

    if(k==i)
      max = i+1;
  }

  return max;

}



int main() {

  char str1[100];
  char str2[100];

  gets(str1);
  gets(str2);

  printf("max isomorphic prefix : %d",isomorphic_prefix(str1,str2));

  return 0;
}