Find longest substring in a string

Question

I'd like to know how to do this:

string1= "cggt"
string2="ccgg"

The max substring string1 contains string2 is only one "c" (string1 must have continue string2 segments like if string1 is "ccgt", then return should be maxsubstring "cc").

More example:

string1:"EggAndApple"  
string2:"AppleEggAnd"

I want to find max substring in string1 contains string2 should be"Apple" (Must started with beginning of string2)

But my code below will give "EggAnd" as result

I searched some solution to return the result maxsubstring is "cgg". The code is

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

How to modify this code to meet my requirements or how to write new segment of code to solve my problem?

Answer 1

Below is my modification for your question, I did not compile and run, but it should work.

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