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

問題描述

給定字符串 s1, s2 (長度 < 100,000)。若 s1 循環移位後包含 s2，則稱 s2 是 s1 的親和串。多測試用例，EOF 結束。

核心觀察

s1 循環移位的所有可能結果，都是字符串 s1 + s1 的子串（長度為 |s1|）。

例如 s1="AABCD"，s1+s1="AABCDAABCD"，所有循環移位：AABCD, ABCDA, BCDAA, CDAAB, DAABC —— 均為其子串。

解法一：KMP 算法 (O(n))

#include 
#include 

const int MAXN = 100005;
char s1[MAXN], s2[MAXN], s3[MAXN*2];
int nxt[MAXN];

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

bool kmpSearch(const char* text, int n, const char* pat, int m) {
    getNext(pat, m);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || text[i] == pat[j]) { ++i; ++j; }
        else j = nxt[j];
    }
    return j == m;
}

int main() {
    while (scanf("%s", s1) == 1) {
        scanf("%s", s2);
        int len1 = strlen(s1), len2 = strlen(s2);
        if (len2 > len1) { puts("no"); continue; }
        strcpy(s3, s1);
        strcat(s3, s1);
        puts(kmpSearch(s3, 2*len1, s2, len2) ? "yes" : "no");
    }
    return 0;
}

解法二：庫函數 strstr (工程實用)

int main() {
    char s1[MAXN], s2[MAXN], s3[MAXN*2];
    while (scanf("%s%s", s1, s2) == 2) {
        strcpy(s3, s1);
        strcat(s3, s1);
        puts(strstr(s3, s2) ? "yes" : "no");
    }
    return 0;
}

strstr 內部通常實現為 Two-Way 或 Boyer-Moore，實際性能極佳，代碼最簡潔。

關鍵邊界條件

• 長度檢查：|s2| > |s1| 直接 "no"
• 空串處理：題目隱含非空，但代碼應健壯
• 大小寫敏感：題目樣例大寫，按 ASCII 精確匹配

複雜度