Light OJ 1334 Genes in DNA：KMP + DP 解決子串前後綴組合計數

問題分析

給定文本串 S 和模式串 P。P 的所有非空真前綴與非空真後綴組成 (n-1)² 個組合串。求 S 中有多少子串等於某個組合串（一個子串可對應多個組合）。

核心洞察

組合串 = 前綴 + 後綴。枚舉相鄰字符對 (c_i, c_i+1)，答案為：

Σ [以 c_i 結尾的前綴數] × [以 c_i+1 開頭的後綴數]

算法流程

1. 正向 KMP：計算 dp1[j] = 模式串前 j 字符中以 P[j-1] 結尾的前綴數
2. 反向 KMP：對反轉串同理計算 dp2
3. 文本串匹配：正向匹配得 l[i] = S[0..i-1] 結尾匹配的前綴數；反向匹配得 r[i]
4. 組合計算：ans = Σ l[i] × r[n-i]

關鍵代碼實現

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 50010;
int l[MAXN], r[MAXN], f[MAXN];
int dp1[MAXN], dp2[MAXN];
char s1[MAXN], s2[MAXN];

// KMP 失敗函數 + DP 計算前綴數
void getFail(char* p, int* dp) {
    int m = strlen(p);
    f[0] = f[1] = 0;
    dp[0] = 0; dp[1] = 1;
    for (int i = 1; i < m; ++i) {
        int j = f[i];
        while (j && p[i] != p[j]) j = f[j];
        f[i+1] = (p[i] == p[j]) ? j+1 : 0;
        dp[i+1] = (p[i] == p[j]) ? dp[j+1] + 1 : 1;
    }
}

// 匹配過程記錄每個位置的匹配數
void find(char* s1, char* s2, int* dp, int* a) {
    int n = strlen(s1), m = strlen(s2);
    int j = 0;
    for (int i = 0; i < n; ++i) {
        while (j && s1[i] != s2[j]) j = f[j];
        if (s1[i] == s2[j]) ++j;
        a[i+1] = dp[j];
        if (j == m) { a[i+1]--; j = f[j]; }
    }
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        scanf("%s %s", s1, s2);
        int n = strlen(s1), m = strlen(s2);

        getFail(s2, dp1);
        find(s1, s2, dp1, l);

        reverse(s1, s1+n);
        reverse(s2, s2+m);
        getFail(s2, dp2);
        find(s1, s2, dp2, r);

        long long ans = 0;
        for (int i = 1; i < n; ++i)
            ans += 1LL * l[i] * r[n-i];

        printf("Case %d: %lld\n", cas, ans);
    }
    return 0;
}

關鍵技術點

1. KMP 失敗函數增強：dp[i] 記錄以 i-1 結尾的前綴出現次數
2. 雙向處理：正向解決前綴，反向解決後綴（本質相同）
3. 邊界處理：完全匹配時 a[i+1]-- 避免重複計數
4. 長長整型：答案可能超過 32 位

複雜度

• 時間：O(|S| + |P|)
• 空間：O(|S| + |P|)

本題巧妙結合 KMP 字符串匹配與動態規劃計數，是字符串問題中「正反雙向 + 狀態增強」的經典範例。