Codeforces 526 D
题意:给一个字符串,求每个前缀是否能表示成\(A+B+A+B+\dots+A\)(\(k\)个\(A+B\))的形式。
思路1:求出所有前缀的哈希值,以便求每个子串的哈希值。然后枚举\(A+B\)的长度,二分\(A\)的长度,用哈希检查一下字符串是否相等即可。
思路2:求出KMP的\(fail\)数组,然后枚举前缀的长度\(len\),看该前缀的最小循环节\(min=len-fail_{len}\)(因为\(A+B+A+B+\dots+A+B+A\)中前缀\(A+B+A+B+\dots+A\)与后缀相等,所以\(A+B\)的长度就是如此求出),
则\(|A+B|=q\times min\),
所以\(len=k\times|A+B|+|A|=k\times q\times min+x\ (0\leq x\leq q\times min)\)。
然后得\(k\times q\times min\leq len\leq (k+1)\times q\times min\)。
所以\(\frac{len}{(k+1)\times min}\leq q\leq \frac{len}{k\times min}\)
那么既然\(q\)为整数,则\(q\)在\([\lceil \frac{len}{(k+1)\times min}\rceil,\lfloor \frac{len}{k\times min}\rfloor]\)中。
进行判断即可。
思路3:同样求出KMP的\(fail\)数组。然后构建\(i\)跳转\(2^j\)次\(fail\)后得到的位置的倍增表,枚举前缀的长度\(len\)。
对于一个前缀,\(|A+B|\)最极端的情况是\(A\)为空或\(B\)为空,两种情况分别\(|A+B|\)为\(\frac{len}{k}\)和\(\frac{len}{k+1}\),所以可以求出\(|A+B|\)的范围。下面只要看通过倍增表是否能从\(len\)跳至\(len-|A+B|\)的范围即可。
思路4:\(Z\_Algorithm\)求出\(Z\)数组表示与前缀向后最长匹配长度,然后枚举\(|A+B|\),判断是否循环\(k\)次,再将最后一个\(A\)可取的最长长度通过\(Z\)数组算出,差分区间修改每一个前缀是否可以即可。