求两个串中的第一个最长子串

本文主要是介绍求两个串中的第一个最长子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：求两个串中的第一个最长子串（神州数码以前试题）。如"abractyeyt","dgdsaeactyey"的最大子串为"actyey"。

#include <iostream>

#include <string>


using namespace std;


//两个串中的第一个最长子串
string FindLongestCommonSubString(string strOne, string strTwo)
{
    if ("" == strOne || strOne.length() <= 0 || "" == strTwo || strTwo.length() <= 0)
    {
        return NULL;
    }
    if (strOne.length() < strTwo.length())  //strOne始终是最长的, 相当于母串，strTwo相当于子串
    {
        string strTmp = strOne;
        strOne = strTwo;
        strTwo = strTmp;
    }
    int *mask = new int[strOne.length()];
    int maxlength = 0;
    int end = -1;
    memset(mask, 0, sizeof(int)*strOne.length());
    for (int i = 0; i < strTwo.length(); i++)
    {
        for (int j = strOne.length() - 1; j >= 0; j--)
        {    
            if (strTwo[i] == strOne[j])
            {
                if (i == 0 || j == 0)
                {
                    mask[j] = 1; //母串为第一个元素，或者子串只有一个元素
                }
                else
                {
                    mask[j] = mask[j - 1] + 1;
                }
            }
            else
            {
                mask[j] = 0;
            }
            if (mask[j] > maxlength)
            {
                maxlength = mask[j];
                end = j;
            }
        }
    }
    delete [] mask;
    return strOne.substr(end - maxlength + 1, maxlength);
}


int main()
{
    string strOne = "abractyeyt";
    string strTwo = "dgdsaeactyey";
    cout<<"第一个字符串: "<<strOne<<endl;
    cout<<"第二个字符串: "<<strTwo<<endl;
    cout<<"最长公共子串: "<<FindLongestCommonSubString(strOne, strTwo);


    cout<<endl;
    return 0;
}

这篇关于求两个串中的第一个最长子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---