Submission #35515406

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/string>
#include <atcoder/segtree>
using namespace atcoder;

int op(int a, int b) { return min(a, b); }
int e() { return (int)1e9; }

int N;
string S, T, U;
vector<int> sa, lcpa, sa_inv;
segtree<int, op, e> seg;

// f(S, i) ≤ f(T, j) か？
bool leq(int i, int j)
{
  int l = sa_inv[i], r = sa_inv[2 * N + j];
  if (l > r)
    swap(l, r);
  int len = seg.prod(l, r); // 一致している長さ
  if (len >= N) // N 文字一致していたら等しい
    return true;
  return U[i + len] <= U[2 * N + j + len]; // 一致しない最初の文字を比較
}

int main()
{
  cin >> N >> S >> T;
  U = S + S + T + T;

  // f(S, i) ≤ f(T, j) かを判定するために必要な情報を求める
  // sa_inv[i] は i が sa のどこにあるかを表す
  sa = suffix_array(U);
  lcpa = lcp_array(U, sa);
  sa_inv.resize(4 * N);
  for (int i = 0; i < 4 * N; i++)
  {
    sa_inv[sa[i]] = i;
  }
  seg = segtree<int, op, e>(lcpa);

  // f(T, P[i]) ≤ f(T, P[i + 1]) を満たす順列 P を求める
  vector<int> P;
  vector<int> sa2 = suffix_array(T + T);
  for (int i = 0; i < 2 * N; i++)
  {
    if (sa2[i] < N)
      P.push_back(sa2[i]);
  }

  long long ans = 0;
  for (int i = 0; i < N; i++)
  {
    // f(S, i) ≤ f(T, P[k]) を満たす k の境界を二分探索で求める（満たすほうが ok で満たさないほうが ng）
    int ok = N, ng = -1;
    while (abs(ok - ng) > 1)
    {
      int mid = (ok + ng) / 2;
      if (leq(i, P[mid]))
        ok = mid;
      else
        ng = mid;
    }
    int tmp = N - ok; // 満たすものの個数
    ans += tmp;
  }
  cout << ans << endl;
}

Submission Info

Judge Result