HDU 4749 Parade Show：KMP 算法變形求最佳觀賞隊列數

問題背景

HDU 4749 Parade Show 是一道經典的 KMP 算法變形題。問題要求從 n 名身高各不相同的學生（身高值 1~k，k ≤ 25）中選出 m 名組成隊列，使得該隊列在任意兩名學生之間的相對高度關係（大、小、等）與原序列中對應位置的關係完全一致。求滿足條件的隊列數量。

核心洞察：相對高度關係的等價轉換

傳統 KMP 匹配的是字符是否相等。本題中，「匹配」定義為：當前前綴已匹配長度為 j，若加入新字符後，前 j+1 個字符中比新字符小的個數、等於的個數、大於的個數分別與模式串前 j+1 個字符中對應統計量相等，則視為匹配成功。

因為身高範圍較小（k ≤ 25），我們可以預處理前綴和，快速計算任意區間內各身高值的出現次數，從而在 O(k) 時間內判斷兩個位置是否「匹配」。

算法流程

1. 預處理前綴和：
   • sum1[h][i]：主序列前 i 個位置中身高為 h 的個數。
   • sum2[h][j]：模式串前 j 個位置中身高為 h 的個數。
2. 判斷函數 judge(i, j)：
   • 統計主序列位置 i 及其前 j 個字符中，比 seq[i] 小/等的個數。
   • 統計模式串位置 j 及其前 j 個字符中，比 seq1[j] 小/等的個數。
   • 兩組統計量全等則返回 true。
3. 構建 Next 數組：對模式串自身運行 KMP 預處理，利用 judge 替代字符比較。
4. KMP 匹配主序列：同標準 KMP，將字符比較替換為 judge，統計匹配次數。

關鍵代碼片段

bool judge(int i, int j, int sum1[][N], int sum2[][N], int *seq, int *seq1) {
    int eq1 = 0, lt1 = 0, eq2 = 0, lt2 = 0;
    for (int x = 1; x <= k; x++) {
        if (x < seq[i]) lt1 += sum1[x][i] - sum1[x][i - j];
        else if (x == seq[i]) eq1 += sum1[x][i] - sum1[x][i - j];
        if (x < seq1[j]) lt2 += sum2[x][j];
        else if (x == seq1[j]) eq2 += sum2[x][j];
    }
    return (lt1 == lt2 && eq1 == eq2);
}

void get_next(int *seq, int m) {
    memset(next, 0, sizeof(next));
    int j = 0;
    for (int i = 2; i <= m; i++) {
        while (j > 0 && !judge(i, j + 1, sum2, sum2, seq1, seq1)) j = next[j];
        if (judge(i, j + 1, sum2, sum2, seq1, seq1)) j++;
        next[i] = j;
    }
}

int kmp(int *seq, int *seq1, int n, int m) {
    int j = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        while (j > 0 && !judge(i, j + 1, sum1, sum2, seq, seq1)) j = next[j];
        if (judge(i, j + 1, sum1, sum2, seq, seq1)) j++;
        if (j == m) { ans++; j = 0; }
    }
    return ans;
}

複雜度分析

• 時間：O((n + m) × k)，k ≤ 25 為常數，實際為線性。
• 空間：O(k × n) 存儲前綴和。

總結

本題巧妙地將「相對順序關係」轉化為可通過前綴和快速比較的統計特徵，使得 KMP 算法能夠處理非精確字符匹配的問題。這是一種將領域知識（相對大小關係不變）融入經典算法的典型範例。