• 定义一个翻转操作\(f(S_n)\)，表示对于一个字符串\(S_n\)，
    有\(f(S)= \{S_1,S_2,…,S_{n-1},S_n,S_{n-1},…S_2,S_1 \}\)。
  • 现在给定一个长度为\(n\)的字符串\(S^{‘}\)表示原字符串\(S\)经过若干次（可能为0）旋转之后的一个前缀，
    求原来字符串可能的长度\(l\)。
  • 显然当\(l > n\)时一定可行，所以只需要输出所有的\(l\leq n\)即可。
    \(|S|\leq 10^6，\Sigma |S| \leq 5 \times 10^6\)

首先想到用 \(Manacher\) 。
由于进行翻转操作后回文串长度必定为奇数，所以不用插入字符，然后考虑什么情况下长度是可行的。

  • 我们定义一个 \(flag\) 数组，\(flag[i]\) 表示长度为 \(i\) 时是可行的。回文数组为\(p\)，\(p[i]\)表示第 \(i\) 位的回文半径位 \(p[i]\)
  • 如果只进行了一次翻转操作即可使得前缀为\(S^{‘}\)，那么有 \(i + p[i] – 1 == n\)
  • 如果需要进行\(k\)次翻转才可以使得前缀为\(S^{‘}\),那么有 \(i – p[i] + 1 == 1\)，然后可以转化为进行\(k – 1\)次的情况。
    但是实际操作中我们不用跑 \(k\) 次，只需要倒着跑并记录 \(flag\) ，因为当我们处理长度为 \(i\) 的时候，\(flag[i + 1]\) 到 \(flag[n]\) 都已经处理过了，所以判断 \(flag[i + p[i] – 1] == 1\)即可。
  • 时间复杂度为\(O(n)\)。
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. #define reg register
  5. namespace io {
  6. char ch[20];
  7. template<typename T>inline void write(T x) {
  8.   (x < 0) && (x =- x, putchar('-'));
  9.   (x) || putchar('0');
  10.   reg int i = 0;
  11.   while (x) ch[i++] = x % 10 ^48, x /= 10;
  12.   while (i) putchar(ch[--i]);
  13. }
  14. }//快写
  15. #define wt io::write
  16. const int maxN = 1000010;
  17. char s[maxN];
  18. int p[maxN], flag[maxN];
  19. int n;
  20. void work();
  21. int main() {
  22.   int t;
  23.   scanf("%d", &t);
  24.   while (t--) work();
  25.   return 0;
  26. }
  27. void work() {
  28.   for (reg int i = 1; i <= n; ++i) flag[i] = p[i] = s[i] = 0;
  29.   n = 1; s[0] = '@';
  30.   scanf("%s", s + 1);
  31.   while (s[n]) ++n;
  32.   --n;
  33.   for (reg int i = 1, r = 0, mid = 0; i <= n; ++i) {
  34.     if (i <= r) p[i] = min(p[mid * 2 - i], r - i + 1);
  35.     while (s[i + p[i]] == s[i - p[i]]) ++p[i];
  36.     if (i + p[i] - 1 >= r) r = i + p[i] - 1, mid = i;
  37.   }//Manacher
  38.   for (reg int i = n; i; --i) {
  39.     if (i + p[i] - 1 == n || (flag[i + p[i] - 1] && i - p[i] + 1 == 1)) flag[i] = 1;
  40.   }//上面说的两种情况
  41.   for (reg int i = 1; i <= n; ++i)
  42.     if (flag[i]) wt(i), putchar(' ');
  43.   putchar('\n');
  44. }

版权声明：本文为LitDarkness原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/LitDarkness/p/15203371.html