string/all_pair_lcp.hpp

• View this file on GitHub
• Last update: 2023-09-02 04:19:30+09:00
• Include: #include "string/all_pair_lcp.hpp"

Verified with

• test_atcoder/abc141e.test.cpp

Code

// dp[i][j] = lcp(S[i:], T[j:])
template <typename STRING>
vvc<int> all_pair_lcp(STRING& S, STRING& T) {
  int N = len(S), M = len(T);
  vv(int, dp, N, M);
  FOR_R(i, N) FOR_R(j, M) {
    if (S[i] != T[j]) continue;
    dp[i][j] = 1 + (i + 1 < N && j + 1 < M ? dp[i + 1][j + 1] : 0);
  }
  return dp;
}

#line 1 "string/all_pair_lcp.hpp"
// dp[i][j] = lcp(S[i:], T[j:])
template <typename STRING>
vvc<int> all_pair_lcp(STRING& S, STRING& T) {
  int N = len(S), M = len(T);
  vv(int, dp, N, M);
  FOR_R(i, N) FOR_R(j, M) {
    if (S[i] != T[j]) continue;
    dp[i][j] = 1 + (i + 1 < N && j + 1 < M ? dp[i + 1][j + 1] : 0);
  }
  return dp;
}

Back to top page