c++ - strings prefix isomorphism with max length -

c++ - strings prefix isomorphism with max length -

string s1 , s2 isomorphic means—— if create 2 string rings,the 2 rings same. example:"abcd" , "cdab" isomorphic ”abcd“ , "dcba" not isomrphic "cdab" , "abdc" not too.

now have 2 strings, output max length create prefixs of 2 strings length isomorphic.

example:"abcdx" , "cdabz" max length 4.

time complexity low possible.

ps: length of 2 strings same

here wrong solution,but passed 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; homecoming 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); homecoming 0; }

ps:there may no o(n) solution problem , o(n) solution exists when 1 of strings minimum representation.

i think can solve using next method :-

1. find longest prefix each substring string1[0 i] suffix substring string2[0 i] , visa versa.lets phone call them lps1[i] & lps2[i]. 2. if lps1[i] + lps2[i] == i+1 prefix upto isomorphic illustration :- 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 largest prefix isomorphic of length 3+1 = 4

now main question how find lps efficiently ?

kmp uses similar algorithm build table in o(|s|). check part table-building algorithm constructs lps string can replace

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

by:-

if string1[ pos-1 ] = string2[cnd] corner checks cnd < string2.length

time complexity :-

build lps arrays : o(|s1|+|s2|) check isomorphic prefix : o(min(|s1|,|s2|)

here 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 = 0;i < n;i++) { int k = lps1[i]+lps2[i]; if(k==i) max = i+1; } homecoming max; } int main() { char str1[100]; char str2[100]; gets(str1); gets(str2); printf("max isomorphic prefix : %d",isomorphic_prefix(str1,str2)); homecoming 0; }

c++ string algorithm