题解 | #查找两个字符串a,b中的最长公共子串#

#include<iostream>
#include<string>

using namespace std;

int main() {
    string a, b;
    getline(cin, a);
    getline(cin, b);
    if (a.size() > b.size()) {
        swap(a, b);//a为长度短的字符串
    }
    if (b.find(a) != string::npos) { //如果a在b中
        cout << a << endl;
    } else {
        int i, j;
        int count_ij = 1;//记录当前最长公共子串长度
        string s, t;
        for (i = 0; i < a.size(); ++i) {
            for (j = 1; j <= a.size() - i; ++j) {
                t = a.substr(i, j);//t: a[i]-a[i+j-1]，一开始为a[0]
                if (b.find(t) == string::npos) { //t不在b里就中止循环
                    if (count_ij < t.size() - 1) { //t长度大于最长子串长度
                        s = a.substr(i, j - 1);
                        count_ij = s.size();
                    }
                    break;
                }
            }
            //已经遍历到最后一个字符但是t还在b里面
            if (j - 1 == a.size() - i) {
                if (count_ij < t.size()) {
                    s = t;
                    count_ij = s.size();
                }
                break;
            }
        }
        cout << s << endl;
    }
    return 0;
}

本题的思路是遍历较短的字符串，找到最长的公共子串