题解 | #公共子串计算#

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

// 初始化一个数组用来滚动保存状态，st[k]表示以a串m索引字符开头和b串n索引字符开头的长度为k的状态，
// true表示这个长度的字符串满足公共字符串要求。
bool st[152];

int main() {
    string a, b;
    cin >> a >> b;
    int m = a.length();
    int n = b.length();
  // 记录可能的公共字符串长度，用于遍历。
    int minlen = min(m, n);
  // 记录结果。
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
		  // 初始化状态。
            memset(st, false, sizeof(st));
		  // 临界状态，长度为0的字符串肯定满足要求。
            st[0] = true;
            for (int k = 1; ((i + k - 1) < m) && ((j + k - 1) < n); k++) {
			  // 状态转移，当且仅当前ab串字符相等，并且上个状态也满足才能转移。
                if (st[k - 1] && (a[i + k - 1] == b[j + k - 1])) {
				  // 更新结果。
                    res = max(res, k);
                    st[k] = true;
                }
            }
        }
    }
    cout << res;
}
// 64 位输出请用 printf("%lld")