题目
HDU-6863
题意
给出一个长度为n的字符串，对于n的每个因子，如果存在一个因子k，将字符串分隔成k个子串，每个子串长度都为n/k，并且每个子串都属于一个cyclical isomorphic，那么就输出Yes，如果所有分隔情况都不能使每个子串为一个cyclical isomorphic则输出No；
cyclical isomorphic：
如果两个串可以通过移动前缀到串的尾部，使得两个串相同，则这两个串为cyclical isomorphic，
例如，a串:“abcd”，b串:“cdab”，将a串的前缀"ab"移动到尾部得到"cdab"，此时ab两个串完全相同，称两串为同一个
题解
这道题目其实是个暴力，我们先枚举n的每个因子k，我们设原字符串最左边的第一个长度n/k的子串为P，将P复制一遍接在尾部，得到得到一个长度为2*n/k的字符串S（S的子串就包含了P的cyclical isomorphic每种情况），我们将S作为待匹配串，遍历分隔得到每个子串Pi，将Pi作为模式串，然后跑kmp，如果每个Pi都是S的子串，则他们都属于一个cyclical isomorphic；
例如：
如图，将原串按照k=4分隔得到4的子串，取第一个串"ab"，复制一遍得到S=“abab”
再遍历Pi，把Pi作为模式串，S作为待匹配串跑KMP，如果每个Pi都是S的子串，则输出Yes，否则枚举下一个因子k，如果没有一个因子都不符合则输出No
代码
/** @author: arc* @date: 2020-08-16 16:10:34*/
#include<cstdio>
using namespace std;
const int maxn = 4e6+5;int Next[maxn];
char S[maxn], P[maxn];void getNext(char *p, int len, int __next[]){//p模式串，下标从0开始int j = 0, k = -1;__next[0] = -1;while(j < len){if(k == -1 || p[j] == p[k]){k++;j++;if(p[j] != p[k]){__next[j] = k;}else{__next[j] = __next[k];}}else{k = __next[k];}}
}int kmp(char *s, char *p, int len_s, int len_p, int __next[]){//s待匹配串，p模式串，下标从0开始int i = 0, j = 0;while(i < len_s && j < len_p){if(j == -1 || s[i] == p[j]){i++;j++;}else{j = __next[j];}}if(j == len_p)return i - j;//数组下标从0开始， 从1开始i-j+1elsereturn -1;//无子串
}int main(){int cas;scanf("%d", &cas);while (cas--) {int n;scanf("%d", &n);scanf("%s", &P);int yes = 0;for (int k = 2; k <= n; k++) {if(n % k == 0){int len_p = n / k;int len_s = len_p * 2;int ok = 1;for (int j = 0; j < len_p; j++) {S[j] = P[j];S[j + len_p] = P[j];}for (int j = 0; j < k; j++) {getNext(P + (j * len_p), len_p, Next);if (kmp(S, P + (j * len_p), len_s, len_p, Next) == -1) {ok = 0;break;}}if (ok) {yes = 1;break;}}}if (yes) {printf("Yes\n");} else {printf("No\n");}}return 0;
}