HDU 2203 親和串：KMP 判斷循環移位包含關係

題目大意

給定字符串 s1, s2 (長度 < 100,000)。若 s1 循環移位後包含 s2，則稱 s2 是 s1 的親和串。多組測試，輸出 yes/no。

核心思路

s1 循環移位後的所有字符串，都是 s1+s1 的子串。因此問題轉化為：判斷 s2 是否為 s1+s1 的子串。

演算法步驟

1. 讀入 s1, s2
2. 構造 s1' = s1 + s1
3. 對 s2 計算 KMP next 數組
4. 在 s1' 上用 KMP 匹配 s2
5. 匹配成功輸出 yes，否則 no

關鍵點

• s1+s1 長度 2n，KMP 匹配 O(n)，總體 O(n) 線性
• 注意字符串結尾添加 '\0'
• 多組測試輸入，用 ~scanf 循環讀取

完整代碼

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define N 200005
char s1[N], s2[N];
int nxt[N];

void getFail(char *p) {
    int len = strlen(p);
    nxt[0] = -1;
    int i = 0, j = -1;
    while (i < len) {
        if (j == -1 || p[i] == p[j]) { i++; j++; nxt[i] = j; }
        else j = nxt[j];
    }
}

bool kmp(char *text, char *pat) {
    int n = strlen(text), m = strlen(pat);
    int i = 0, j = 0;
    while (i < n) {
        if (j == -1 || text[i] == pat[j]) { i++; j++; }
        else j = nxt[j];
        if (j == m) return true;
    }
    return false;
}

int main() {
    while (~scanf("%s%s", s1, s2)) {
        int len = strlen(s1);
        for (int i = 0; i < len; i++) s1[len + i] = s1[i];
        s1[2 * len] = '\0';
        getFail(s2);
        if (kmp(s1, s2)) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

複雜度分析

每組測試：構造 s1+s1 O(n)，KMP 預處理 O(m)，匹配 O(n+m)。總時間 O(n)，空間 O(n)，滿足 100,000 長度限制。