查找最長的子字符串中的

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);