Pattern 5: Longest Common Substring code example

Example: The longest common suffix

//
void LongestCommenSubstring(std::string str1, std::string str2)
{
    const int m = str1.length();
    const int n = str2.length();
    int lcs[m][n];

    for(int i = 0; i < m; ++i)
    {
        for(int j = 0; j < n;++j)
        {
            lcs[i][j] = 0;
        }
    }

    for(int i = 0; i < m; ++i)
    {
        for(int j = 0; j < n;++j)
        {
            if(str1[i] == str2[j])
            {
                if((i-1 >= 0 ) && ( j-1 >= 0))
                {
                    if(str1[i-1] == str2[j-1])
                    {
                        lcs[i][j] = lcs[i-1][j-1]+1;
                    }
                }
            }
            else
            {

                if((i-1 >= 0 ) &&( j-1 >= 0))
                {
                    lcs[i][j] = std::max(lcs[i][j-1], lcs[i-1][j]);
                }
            }
        }
    }
   std::cout << "longest commen substring" << lcs[m-1][n-1];}
}
//

Tags:

Misc Example