c++ - 最大长度的字符串前缀同构

Question

字符串s1和s2是同构的意思——如果我们把这两个字符串做成环，这两个环是一样的。示例:“abcd”和“cdab”是同构的“abcd”和“dcba”不是同构的"cdab"和 "abdc"不太一样。

现在你有两个字符串，输出一个最大长度，使两个字符串的前缀长度同构。

示例:“abcdx”和“cdabz”最大长度为 4。

时间复杂度尽可能低。

PS:两个字符串的长度是一样的

这是一个错误的解决方案，但通过了所有测试

#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:这个问题可能没有O(n)的解，O(n)的解只有当其中一个字符串是它的最小表示时才存在。

Answer 1

我认为您可以使用以下方法解决此问题:-

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

现在的主要问题是如何有效地找到lps？

KMP使用类似的算法在 O(|S|) 中建表。检查建表算法部分，它基本上用自身构造字符串的lps，但你可以替换

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

作者:-

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

with some corner checks like cnd < string2.length

时间复杂度:-

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

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

这是 C++ 实现:-

#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;
}