NYOJ 327 親和串：KMP 算法判斷循環同構（s1+s1 包含 s2）

判斷 s2 是否為 s1 的循環移位子串。即：s1+s1 中是否包含 s2。KMP 算法 O(n+m) 求解。

KMP 核心

• next[] 數組：模式串最長公共前後綴長度
• 構建 next：next[0]=-1，匹配失敗時跳轉
• 匹配：主串 s1+s1，模式串 s2

完整代碼

#include <cstdio>
#include <cstring>
#define maxn 100005
char str1[2*maxn], str2[maxn];
int next[maxn], len1, len2;

void getNext() {
    int i=0, j=-1; next[0]=-1;
    while (i

關鍵點

長度檢查：len1 < len2 直接 no
memcpy 將 str1 複製到自身後方，構造 s1+s1
KMP 模板可直接套用於所有字符串匹配問題

經典的「循環同構」判斷轉化為「字符串包含」問題，KMP 是線性時間解法。