結果

問題 No.263 Common Palindromes Extra
コンテスト
ユーザー SSRS
提出日時 2022-08-31 03:34:27
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,950 bytes
コンパイル時間 2,294 ms
コンパイル使用メモリ 192,620 KB
実行使用メモリ 103,852 KB
最終ジャッジ日時 2024-11-07 20:10:55
合計ジャッジ時間 9,853 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const long long BASE = 123456789;
const long long M30 = ((long long) 1 << 30) - 1;
const long long M31 = ((long long) 1 << 31) - 1;
const long long MOD = ((long long) 1 << 61) - 1;
unsigned long long modulo(unsigned long long x){
  unsigned long long xu = x >> 61;
  unsigned long long xd = x & MOD;
  unsigned long long res = xu + xd;
  if (res >= MOD){
    res -= MOD;
  }
  return res;
}
unsigned long long mul(unsigned long long a, unsigned long long b){
  unsigned long long au = a >> 31;
  unsigned long long ad = a & M31;
  unsigned long long bu = b >> 31;
  unsigned long long bd = b & M31;
  unsigned long long mid = au * bd + ad * bu;
  unsigned long long midu = mid >> 30;
  unsigned long long midd = mid & M30;
  return modulo(au * bu * 2 + midu + (midd << 31) + ad * bd);
}
struct rolling_hash{
  vector<long long> POW, S;
  rolling_hash(string s){
    int N = s.size();
    POW.resize(N + 1);
    POW[0] = 1;
    for (int i = 0; i < N; i++){
      POW[i + 1] = mul(POW[i], BASE);
    }
    S.resize(N + 1);
    S[N] = 0;
    for (int i = N - 1; i >= 0; i--){
      S[i] = modulo(mul(S[i + 1], BASE) + s[i]);
    }
  }
  long long get(int L, int R){
    return modulo(S[L] + MOD - mul(S[R], POW[R - L]));
  }
};
vector<int> manacher(string &S){
  int N = S.size();
  vector<int> ans(N, 0);
  int i = 0, j = 0;
  while (i < N){
    while (i >= j && i + j < N && S[i - j] == S[i + j]){
      j++;
    }
    ans[i] = j;
    int k = 1;
    while (i >= k && i + k < N && k + ans[i - k] < j){
      ans[i + k] = ans[i - k];
      k++;
    }
    i += k;
    j -= k;
  }
  return ans;
}
vector<int> suffix_array(const vector<int> &A, int mx){
  int N = A.size();
  vector<int> sum(mx + 1, 0);
  for (int i = 0; i < N; i++){
    sum[A[i] + 1]++;
  }
  for (int i = 0; i < mx; i++){
    sum[i + 1] += sum[i];
  }
  vector<bool> is_s(N);
  is_s[N - 1] = false;
  for (int i = N - 2; i >= 0; i--){
    is_s[i] = A[i] < A[i + 1] || A[i] == A[i + 1] && is_s[i + 1];
  }
  vector<int> id(N, -1);
  vector<int> pos;
  int M = 0;
  for (int i = 1; i < N; i++){
    if (is_s[i] && !is_s[i - 1]){
      id[i] = M;
      pos.push_back(i);
      M++;
    }
  }
  vector<int> sa(N);
  auto induce = [&](vector<int>& lms){
    sa = vector<int>(N, -1);
    vector<bool> used(N, false);
    vector<int> p(mx);
    vector<int> p2(mx);
    for (int i = 0; i < mx; i++){
      p[i] = sum[i + 1] - 1;
      p2[i] = sum[i];
    }
    for (int i = M - 1; i >= 0; i--){
      sa[p[A[lms[i]]]] = lms[i];
      p[A[lms[i]]]--;
      used[lms[i]] = true;
    }
    sa[p2[A[N - 1]]] = N - 1;
    p2[A[N - 1]]++;
    used[N - 1] = true;
    for (int i = 0; i < N; i++){
      if (sa[i] > 0){
        if (!is_s[sa[i] - 1] && !used[sa[i] - 1]){
          sa[p2[A[sa[i] - 1]]] = sa[i] - 1;
          p2[A[sa[i] - 1]]++;
          used[sa[i] - 1] = true;
        }
      }
    }
    for (int i = 0; i < N; i++){
      if (sa[i] != -1){
        if (id[sa[i]] != -1){
          used[sa[i]] = false;
          sa[i] = -1;
        }
      }
    }
    for (int i = 0; i < mx; i++){
      p[i] = sum[i + 1] - 1;
    }
    for (int i = N - 1; i >= 0; i--){
      if (sa[i] > 0){
        if (is_s[sa[i] - 1] && !used[sa[i] - 1]){
          sa[p[A[sa[i] - 1]]] = sa[i] - 1;
          p[A[sa[i] - 1]]--;
          used[sa[i] - 1] = true;
        }
      }
    }
  };
  induce(pos);
  if (M == 0){
    return sa;
  }
  vector<int> lms;
  for (int i = 0; i < N; i++){
    if (id[sa[i]] != -1){
      lms.push_back(sa[i]);
    }
  }
  vector<int> c(M);
  c[0] = 0;
  for (int i = 0; i < M - 1; i++){
    c[i + 1] = c[i];
    int x = lms[i];
    int y = lms[i + 1];
    bool ok = true;
    while (x < N && y < N){
      if (A[x] != A[y]){
        ok = false;
        break;
      }
      x++;
      y++;
      if (id[x] != -1){
        if (id[y] == -1){
          ok = false;
        }
        break;
      }
    }
    if (x == N || y == N){
      ok = false;
    }
    if (!ok){
      c[i + 1]++;
    }
  }
  vector<int> rec(M);
  for (int i = 0; i < M; i++){
    rec[id[lms[i]]] = c[i];
  }
  vector<int> sa2 = suffix_array(rec, c[M - 1] + 1);
  vector<int> pos2(M);
  for (int i = 0; i < M; i++){
    pos2[i] = pos[sa2[i]];
  }
  induce(pos2);
  return sa;
}
vector<int> suffix_array(const string &S){
  int N = S.size();
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    A[i] = S[i];
  }
  return suffix_array(A, 256);
}
vector<int> lcp_array(string &S, vector<int> &SA){
  int N = S.size();
  vector<int> rank(N);
  for (int i = 0; i < N; i++){
    rank[SA[i]] = i;
  }
  vector<int> lcp(N - 1, 0);
  int h = 0;
  for (int i = 0; i < N; i++){
    if (rank[i] > 0){
      int prev = SA[rank[i] - 1];
      if (h > 0){
        h--;
      }
      while (i + h < N && prev + h < N){
        if (S[i + h] != S[prev + h]){
          break;
        }
        h++;
      }
      lcp[rank[i] - 1] = h;
    }
  }
  return lcp;
}
template <typename T>
struct sparse_table{
	vector<vector<T>> ST;
	sparse_table(vector<T> &A){
		int N = A.size();
		int LOG = 32 - __builtin_clz(N);
		ST = vector<vector<T>>(LOG, vector<T>(N));
		for (int i = 0; i < N; i++){
			ST[0][i] = A[i];
		}
		for (int i = 0; i < LOG - 1; i++){
			for (int j = 0; j < N - (1 << i); j++){
				ST[i + 1][j] = min(ST[i][j], ST[i][j + (1 << i)]);
			}
		}
	}
	T range_min(int L, int R){
		int d = 31 - __builtin_clz(R - L);
		return min(ST[d][L], ST[d][R - (1 << d)]);
	}
};
unordered_map<unsigned long long, int> solve(string S){
  int N = S.size();
  string T = "$";
  for (int i = 0; i < N; i++){
    T += S[i];
    T += '$';
  }
  vector<int> A = manacher(T);
  vector<int> SA = suffix_array(S);
  vector<int> LCP = lcp_array(S, SA);
  sparse_table<int> ST(LCP);
  rolling_hash RH(S);
  vector<int> rank(N);
  for (int i = 0; i < N; i++){
    rank[SA[i]] = i;
  }
  unordered_map<unsigned long long, int> mp;
  for (int i = 1; i < N * 2; i++){
    int l = (i - A[i] + 2) / 2, r = (i + A[i] - 1) / 2;
    while (l < r){
      unsigned long long hash = RH.get(l, r);
      if (mp.count(hash) == 1){
        break;
      }
      int tv1 = rank[l], fv1 = N;
      while (fv1 - tv1 > 1){
        int mid = (tv1 + fv1) / 2;
        if (ST.range_min(rank[l], mid) >= r - l){
          tv1 = mid;
        } else {
          fv1 = mid;
        }
      }
      int tv2 = rank[l], fv2 = -1;
      while (tv2 - fv2 > 1){
        int mid = (tv2 + fv2) / 2;
        if (ST.range_min(mid, rank[l]) >= r - l){
          tv2 = mid;
        } else {
          fv2 = mid;
        }
      }
      mp[hash] = tv1 - tv2 + 1;
      l++;
      r--;
    }
  }
  return mp;
}
int main(){
  string S;
  cin >> S;
  string T;
  cin >> T;
  unordered_map<unsigned long long, int> A = solve(S);
  unordered_map<unsigned long long, int> B = solve(T);
  long long ans = 0;
  for (auto P : A){
    if (B.count(P.first) == 1){
      ans += (long long) P.second * B[P.first];
    }
  }
  cout << ans << endl;
}
0