查找最长的子字符串中的

Question

我想知道如何做到这一点：

string1= "cggt" 
string2="ccgg" 

的最大子string1包含string2只有一个“C”（string1必须继续string2段一样，如果string1是“ccgt”，那么返回应该是maxsubstring“cc”）。

更多例子：

string1:"EggAndApple" 
string2:"AppleEggAnd" 

我想找到最大子在string1包含string2应该是“苹果”（必须开始的string2开始）

但我的代码下面会给“EggAnd”作为结果

我搜索了一些解决方案返回结果maxsubstring是“cgg”。 代码是

int findOverlap(std::string str1, std::string str2) 
    { 
    if(str1.empty() || str2.empty()) 
    { 
      return 0; 
    } 

    int *curr = new int [str1.size()]; 
    int *prev = new int [str1.size()]; 
    int *swap = nullptr; 
    int maxSubstr = 0; 

    for(int i = 0; i<str2.size(); ++i) 
    { 
      for(int j = 0; j<str1.size(); ++j) 
      { 
       if(str1[j] != str2[i]) 
       { 
        curr[j] = 0; 

       } 
       else 
       { 
        if(i == 0) 
        { 
         curr[j] = 1; 
        } 
        else 
        { 
         curr[j] = 1 + prev[j-1]; 
        } 

        if(maxSubstr < curr[j]) 
        { 
         maxSubstr = curr[j]; 
        } 
       } 
      } 
      swap=curr; 
      curr=prev; 
      prev=swap; 
    } 
    delete [] curr; 
    delete [] prev; 
    return maxSubstr; 
} 

如何修改这个代码来满足我的要求，或者如何编写新的代码段，以解决我的问题？

Answer 1

下面是我对你的问题的修改，我没有编译和运行，但它应该工作。

char* str1 = "EggAndApple"; 
char* str2 = "AppleEggAnd"; 

int* maxSubStrLen = new int [strlen(str1)]; 
memset(maxSubStrLen, 0, sizeof(int) * strlen(str1)); 

// start index of max substring 
int maxGlobalSubStrIdx = -1; 
// length of max substring 
int maxGlobalSubStrLen = 0; 

for(int i = 0; i < strlen(str2); ++i) 
{ 
    for(int j = i; j < strlen(str1); ++j) 
    { 
     if(str1[j] != str2[i]) 
     { 
      continue; 
     } 

     // str1[j] == str2[i] 
     { 
      // find substring started from (j - i) ? 
      if(maxSubStrLen[j - i] == i) { 
       maxSubStrLen[j - i]++; 
       if(maxGlobalSubStrLen < maxSubStrLen[j - i]) 
       { 
        maxGlobalSubStrLen = maxSubStrLen[j - i]; 
        maxGlobalSubStrIdx = j - i; 
       } 
      } 
     } 
    } 
} 
delete [] maxSubStrLen; 
printf("maxGlobalSubStrLen:%d, maxGlobalSubStrIdx:%d\n", maxGlobalSubStrLen, maxGlobalSubStrIdx);