【牛客网】查找两个字符串a,b中的最长公共子串

r囧r小猫 2021-12-20 19:47 244阅读 0赞

#### 题目描述 ####

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。  
输入描述：输入两个字符串  
输出描述： 返回重复出现的字符

#### 示例: ####

输入

> abcdefghijklmnop  
> abcsafjklmnopqrstuvw

输出

> jklmnop

#### 解题思路 ####

暴力查找法：先比较两个字符串的长短，将较短的字符串存在s1中。再用两个循环对s1和s2分别进行遍历查找公共子串ret，将目前最长的公共子串存在s中，之后每找到一个公共子串ret都与s进行长度的比较，若比s长则更新s中存的子串，否则继续查找，直至查找到s1的末尾。

#### 完整代码 ####

#include <iostream>
    #include <string>
    using namespace std;
    
    string Find(string s1,string s2)
    {
        string s="";
        for(size_t i=0;i<s1.size();i++)
        {
            string ret="";
            for(size_t j=0;j<s2.size();j++)
            {
                size_t m=i;
                while(s1[m]==s2[j])
                {
                    ret+=s1[m];
                    m++;j++;
                }
                if(ret.size()>s.size())
                    s=ret;
                ret="";
            }
        }
        return s;
    }
    int main()
    {
    	string a;
    	string b;
    	while (cin >> a >> b)
    	{
    		if (a.size() > b.size())
    			swap(a, b);
    		string s=Find(a,b);
    		cout << s << endl;
    	}
    	return 0;
    }

#### 原题链接 ####

https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506?tpId=37&&tqId=21288&rp=1&ru=/activity/oj&qru=/ta/huawei/question-ranking

点关注支持一下博主呗~