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

两个陷阱：

1. 注意题目要求返回的是短串的第一个。
2. 是最长公共字串，不是子序列。所以，在比较晚要max找最大。

#include<bits/stdc++.h>

using namespace std;

int main(){

    string a,b;

    while(cin>>a>>b){
        if(a.size() > b.size())// 若有多个，输出在较短串中最先出现的那个。所以短那个串放到前面，然后外循环以短串为主。这样就能保证题意。
            swap(a,b);

        vector<vector<int>> dp(a.size()+1,vector<int>(b.size()+1,0));//其实其中内嵌了互相为0个字符，这样的话那只能是0

        dp[0][0] = 0;

        int max_ =0, last  = 0;

        for(int i =1; i<= a.size();i++){
            for(int j = 1; j<= b.size();j++){
                if(a[i-1]==b[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{

                    dp[i][j] = 0;//注意，这个题是子串而不是子序列
                }

                if(dp[i][j]>max_){//找最长的那个
                        max_ = dp[i][j];
                        last = i - 1;//这个a和b的索引都可以，但是要看题的要求
                }
            }
        }

        if(max_==0) cout<<"-1"<<endl;//没有公共子串

        cout<<a.substr(last-max_+1,max_)<<endl;//这个a和b的索引都可以，但是要看题的要求

    }


}