查找两个字符串a,b中的最长公共子串 暴力破解法

思路

直接从短串中从长到短取字串，判断子串是否在长串中，如果在长串中，就返回该子串，否则下一个子串。

C++ 实现

#include<iostream>
#include<string>

using namespace std;

string findLongest(string shorts, string longs) {
    int shortSize = shorts.size();
    int count = shortSize;
    string subStr;
    while (count > 0) {
        for (int i = 0; i + count <= shortSize; i++) {
            subStr = shorts.substr(i, count);
            string::size_type pos = longs.find(subStr);
            if (pos != longs.npos) {
                return subStr;
            }
        }
        --count;
    }
    return shorts.substr(0, 1);
}

int main() {
    string str1, str2;
    int shortStr;
    cin >> str1;
    cin >> str2;
    if (str1.size() < str2.size()) {
        shortStr = 1;
    } else {
        shortStr = 0;
    }
    // 从较短的字符串中不停的取子串,在长串中查找子串
    if (shortStr)
        str1 = findLongest(str1, str2);
    else
        str1 = findLongest(str2, str1);
    
    cout << str1;
    return 0;
}