lCS(最长公共子串)

之前一直写的最长公共子序列，从来没写过最长公共子串这个算法，也因为这个，在今年的蓝桥杯省赛中有个题目用的暴力字符串匹配，导致了丢分（也可能拿不到省一了，哎）

其实就是一个二维的dp，dp[i][j]表示第一个以i结尾，第二个以j结尾的最长长度。

1 初始化，第一个串的下标按行存储，第二个串的下标按列存储。第一列按行遍历，表示当前在第一个串s的第i个字符时，t串的第1个字符时，是否相等。
按列遍历，表示s串第一个字符和t串的第j个字符是否相等。

2 状态转移 如果s[i] == t[j] , dp[i][j] = dp[i - 1][j - 1] + 1，否则 = 0;

3 输出结果 在遍历的过程中保留结果即可。

4 拓展 如何输出这个串?在遍历的过程中如果ans被更新，则记录某个串的结尾下标，然后直接按记录的下标-ans输出即可。

void solve(){
string s, t;
cin >> s >> t;

int n = s.size();
int m = t.size();

vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; ++i){
    if (s[i - 1] == t[0]){
        dp[i][1] = 1;
    }
}
for (int i = 1; i <= m; ++i){
    if (t[i - 1] == s[0]){
        dp[1][i] = 1;
    }
}

int ans = 0;
int index = 0;
for (int i = 1; i <= n; ++i){
    for (int j = 1; j <= m; ++j){
        if (s[i - 1] == t[j - 1]){
            dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        else{
            dp[i][j] = 0;
        }
        if (changeMax(ans, dp[i][j])){
            index = i - ans;
        }
    }
}

cout << ans << '\n';
cout << s.substr(index, ans) << '\n';

}