POJ 1226 Substrings：最長公共子串（或反轉）暴力解

題目

給 n (≤100) 個字符串（長度 ≤100），求最長字符串 X，使得 X 或其反轉出現在每個字符串中。輸出長度。

暴力可行性分析

最短字符串長度 ≤100，其子串數 ≤ 5050。對每個子串，檢查是否在其它所有字符串中出現（正向或反向）。總操作 ~ 5050 * 100 * 100 = 5e7，C++ 足夠快。利用 string::find 和 string(rbegin,rend) 反轉。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector s(n);
        int minLen = INT_MAX, minIdx = 0;
        for (int i = 0; i < n; i++) {
            cin >> s[i];
            if (s[i].size() < minLen) { minLen = s[i].size(); minIdx = i; }
        }
        string base = s[minIdx];
        int ans = 0;
        for (int len = minLen; len >= 1; len--) {
            bool found = false;
            for (int i = 0; i + len <= minLen; i++) {
                string sub = base.substr(i, len);
                string rev(sub.rbegin(), sub.rend());
                bool ok = true;
                for (int j = 0; j < n; j++) {
                    if (s[j].find(sub) == string::npos && s[j].find(rev) == string::npos) {
                        ok = false; break;
                    }
                }
                if (ok) { ans = len; found = true; break; }
            }
            if (found) break;
        }
        cout << ans << endl;
    }
    return 0;
}