string/lyndon.hpp

• View this file on GitHub
• Last update: 2025-05-18 18:12:51+09:00
• Include: #include "string/lyndon.hpp"

Required by

• string/lex_min_suffix_for_all_prefix.hpp
• string/non_dominated_suffix.hpp

Verified with

• test/1_mytest/lex_minmax_suffix.test.cpp
• test/2_library_checker/string/lyndon.test.cpp

Code

#pragma once

template <typename CHAR>
struct Incremental_Lyndon_Factorization {
  vc<CHAR> S;
  int i = 0, j = 0, k = 0;
  vc<int> minimum_suffix_len = {0};

  int add(CHAR c) {
    S.eb(c);
    // [j, j+(i-k)) simple
    while (i < len(S)) {
      if (k == i) {
        assert(j == k);
        ++i;
      }
      elif (S[k] == S[i]) { ++k, ++i; }
      elif (S[k] < S[i]) { k = j, ++i; }
      else {
        j += (i - j) / (i - k) * (i - k);
        i = k = j;
      }
    }
    if ((i - j) % (i - k) == 0) {
      minimum_suffix_len.eb(i - k);
    } else {
      minimum_suffix_len.eb(minimum_suffix_len[k]);
    }
    return minimum_suffix_len[i];
  }

  vc<int> factorize() {
    int i = len(S);
    vc<int> I;
    while (i) {
      I.eb(i);
      i -= minimum_suffix_len[i];
    }
    I.eb(0);
    reverse(all(I));
    return I;
  }
};

#line 2 "string/lyndon.hpp"

template <typename CHAR>
struct Incremental_Lyndon_Factorization {
  vc<CHAR> S;
  int i = 0, j = 0, k = 0;
  vc<int> minimum_suffix_len = {0};

  int add(CHAR c) {
    S.eb(c);
    // [j, j+(i-k)) simple
    while (i < len(S)) {
      if (k == i) {
        assert(j == k);
        ++i;
      }
      elif (S[k] == S[i]) { ++k, ++i; }
      elif (S[k] < S[i]) { k = j, ++i; }
      else {
        j += (i - j) / (i - k) * (i - k);
        i = k = j;
      }
    }
    if ((i - j) % (i - k) == 0) {
      minimum_suffix_len.eb(i - k);
    } else {
      minimum_suffix_len.eb(minimum_suffix_len[k]);
    }
    return minimum_suffix_len[i];
  }

  vc<int> factorize() {
    int i = len(S);
    vc<int> I;
    while (i) {
      I.eb(i);
      i -= minimum_suffix_len[i];
    }
    I.eb(0);
    reverse(all(I));
    return I;
  }
};

Back to top page