src/string/manacher.hpp

• View this file on GitHub
• Last update: 2023-07-06 05:59:12+09:00
• Include: #include "src/string/manacher.hpp"

Code

#pragma once

#include <vector>
#include <string>

namespace luz {
  // calculate a sequence of odd-length palindromic radii
  //   centered at each index.
  // e.g. manacher("abac") = (1, 2, 1, 1)
  // to support even-length, insert a dummy character.
  //   [!] be careful with the post-processing.
  //       exec `vs[i] -= ((i ^ vs[i]) & 1) == 0;`
  std::vector<int> manacher(std::string s){
    int n = s.size();
    std::vector<int> vs(n);
    int i = 0, j = 0;
    while (i < n) {
      while (i - j >= 0 and i + j < n and s[i - j] == s[i + j]) j++;
      vs[i] = j;
      int k = 1;
      while (i - k >= 0 and i + k < n and k + vs[i - k] < j) {
        vs[i + k] = vs[i - k];
        k++;
      }
      i += k;
      j -= k;
    }
    return vs;
  }

}

#line 2 "src/string/manacher.hpp"

#include <vector>
#include <string>

namespace luz {
  // calculate a sequence of odd-length palindromic radii
  //   centered at each index.
  // e.g. manacher("abac") = (1, 2, 1, 1)
  // to support even-length, insert a dummy character.
  //   [!] be careful with the post-processing.
  //       exec `vs[i] -= ((i ^ vs[i]) & 1) == 0;`
  std::vector<int> manacher(std::string s){
    int n = s.size();
    std::vector<int> vs(n);
    int i = 0, j = 0;
    while (i < n) {
      while (i - j >= 0 and i + j < n and s[i - j] == s[i + j]) j++;
      vs[i] = j;
      int k = 1;
      while (i - k >= 0 and i + k < n and k + vs[i - k] < j) {
        vs[i + k] = vs[i - k];
        k++;
      }
      i += k;
      j -= k;
    }
    return vs;
  }

}

Back to top page