fork(3) download
copy 
  1. /*
  2.   Copyright 2013 Marek "p2004a" Rusinowski
  3.   Manacher algorithm
  4. */
  5. #include <cstdio>
  6. #include <cstring>
  7. #include <cstdlib>
  8. #include <algorithm>
  9.  
  10. #define MAXN 1000000
  11.  
  12. using namespace std;
  13.  
  14. char str[MAXN];
  15. int R[MAXN];
  16.  
  17. void manacher(char *str, int len, int *R, bool odd) {
  18.   fill(R, R + len, 0);
  19.   for (int k, i = odd; i < len; i += k) {
  20.     while (i + R[i] < len && i - R[i] - odd >= 0 && str[i + R[i]] == str[i - R[i] - odd]) ++R[i];
  21.     for (k = 1; k < R[i] && R[i] - k != R[i - k]; ++k) R[i + k] = min(R[i] - k, R[i - k]);
  22.     R[i + k] = max(min(R[i] - k, R[i - k]), 0);
  23.   }
  24. }
  25.  
  26. int main() {
  27.   int n;
  28.   scanf("%d%s", &n, str);
  29.   for (int j = 0; j < 2; ++j) {
  30.     manacher(str, n, R, j);
  31.     for (int i = 0; i < n; ++i) {
  32.       printf(j ? " %c" : "%c ", str[i]);
  33.     }
  34.     printf("\n");
  35.     for (int i = 0; i < n; ++i) {
  36.       printf("%d ", R[i]);
  37.     }
  38.     printf("\n");
  39.   }
  40.   return 0;
  41. }
  42.  
Success #stdin #stdout 0.01s 7608KB
comments (?)
stdin
copy 
25
aabbabbabbababababbbabaab
stdout
copy 
a a b b a b b a b b a b a b a b a b b b a b a a b 
1 1 1 1 4 1 1 5 1 1 2 3 4 6 4 3 2 1 5 1 2 2 1 1 1 
 a a b b a b b a b b a b a b a b a b b b a b a a b
0 1 0 2 0 0 5 0 0 3 0 0 0 0 0 0 0 0 1 1 0 0 0 2 0
https://ideone.com/b4r4WG
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!