题目链接：点击打开链接
题意：
给出长度为n的字符串，常数k
下面一个长度为n的字符串。
问：
for(int i = 1; i <= n; i++){
字符串的前i个字符 能否构成 形如A+B+A+B+A+B+A的形式，其中A有k+1个，B有k个 A和B是2个任意的字符串（也可以为空串）
若可以构成则输出1，，否则输出0
}
思路：
POJ1961
先用kmp求一个前缀循环节，。
我们观察 ABABABA => AB, AB, AB, A 所以前缀循环节有K个，而后面的A是尽可能地和AB长度接近，所以hash+二分求A的最长长度。
思路2：
直接枚举AB串的长度，然后二分A串的长度即可。
#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <queue>#include <set>#include <map>#include <vector>template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + '0');}using namespace std;const int N = 1000005;typedef long long ll;typedef unsigned long long ull;const int maxn = 2000 * 1000 + 100, base1 = 131, base2 = 127;const int mod = 1000000007;int hash1[maxn], hash2[maxn], p1[maxn], p2[maxn];inline int get(int l, int r){l–;int ret = hash1[r] – 1LL * hash1[l] * p1[r – l ] % mod;if (ret<0)ret += mod;return ret;}int n, k, dp[N];char s[N];void work(){memset(dp, 0, sizeof dp);for (int y = n / k; y; y–){int len = y*k;if (dp[len] != 0)continue;ull now = get(1, y);bool ok = true;for (int j = 2; j <= k && ok; j++){if (get(j*y – y + 1, j*y) != now)ok = false;}if (ok)dp[len]++;else {continue;}int las = len;int l = len + 1, r = min(len + y, n);while (l <= r){int mid = (l + r) >> 1;if (get(1, mid – len) == get(len + 1, mid)){las = max(las, mid);l = mid + 1;}else r = mid – 1;}dp[las + 1] –;}}int hehe;int haha;int main(){p1[0] = 1;for (int i = 1; i<maxn; i++)p1[i] = 1LL * p1[i – 1] * base1%mod;scanf("%d%d", &n, &k);scanf("%s", s + 1);for (int i = 1; i <= n; i++)hash1[i] = (1LL * hash1[i – 1] * base1 + s[i]) % mod;if (k > n){ while (n– > 0)putchar('0'); puts(""); return 0; }work();int now = 0;for (int i = 1; i <= n; i++){now += dp[i];putchar('0' + (now>0));}puts("");return 0;}
那些曾经以为念念不忘的事情就在我们念念不忘的过程里，被我们遗忘了。
