多字符串中尋找最長公共子串（含反轉匹配）的C語言解法

多字符串中尋找最長公共子串（含反轉匹配）的C語言解法

輸入多組測試用例，每組 n 個字符串，找出在所有字符串中均出現（或其反轉出現）的最長子串長度。

優化策略

1. 先找出最短字符串 lina，減少枚舉空間。
2. 從長度 len 遞減到 1，枚舉 lina 所有長度為 len 的子串 str 及其反轉 rts。
3. 檢查 str 或 rts 是否在所有字符串中出現（strstr）。
4. 首個滿足條件即為最長，直接返回長度。

關鍵函數

int fin(char *str, char *rts) {  // 判斷子串是否在所有串中出現
    for (int i=0; i<x; i++)
        if (!strstr(a[i], str) && !strstr(a[i], rts)) return 0;
    return 1;
}

完整主流程

while (n--) {
    linstr();           // 讀入並找最短串
    printf("%d\n", fuck()); // 枚舉驗證輸出長度
}

注意：strrev 非標準函數，部分 OJ 不支持，需自行實現字符串反轉。