結果

問題 No.430 文字列検索
ユーザー ScosaScosa
提出日時 2020-04-21 11:30:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 33 ms / 2,000 ms
コード長 6,685 bytes
コンパイル時間 2,216 ms
コンパイル使用メモリ 177,108 KB
実行使用メモリ 17,968 KB
最終ジャッジ日時 2024-04-16 19:28:20
合計ジャッジ時間 3,170 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 31 ms
17,600 KB
testcase_02 AC 29 ms
17,536 KB
testcase_03 AC 30 ms
17,600 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 20 ms
17,732 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 AC 33 ms
17,840 KB
testcase_12 AC 32 ms
17,720 KB
testcase_13 AC 32 ms
17,968 KB
testcase_14 AC 31 ms
17,832 KB
testcase_15 AC 30 ms
17,692 KB
testcase_16 AC 27 ms
17,792 KB
testcase_17 AC 28 ms
17,664 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int _base = 1e9 + 7;

template<class V> struct SparseTable { // [L,R)
      const V def = 0;
      inline V comp(V a, V b) { return min(a, b); }

      int n; vector<V> a, b[22]; inline int __lg(int x) { return 32 - 1 - __builtin_clz(x); }
      void init(vector<V> v) {
            int nn = v.size(); n = 1; while (n < nn) n *= 2; a.resize(n);
            for (int i = 0; i < 22; i++) b[i].resize(n); for (int i = 0; i < nn; i++) a[i] = v[i];

            int d = 1 << __lg(n - 1), e = d << 1;
            for (int h = 0, f; (f = 1 << h) <= d; ++h) {
                  for (int i = f, r = f << 1; i < e; i += r) {
                        b[h][i - 1] = a[i - 1];
                        for (int j = i - 2; j >= i - f; --j) b[h][j] = comp(b[h][j + 1], a[j]);
                        b[h][i] = a[i];
                        for (int j = i + 1; j < i + f; ++j) b[h][j] = comp(b[h][j - 1], a[j]);
                  }
            }
      }

      V get(int L, int R) {
            assert(0 <= L && L <= R); if (L == R)return def; R--; if (L == R)return a[L]; int h = __lg(L ^ R);
            return comp(b[h][L], b[h][R]);
      }
};
struct SuffixArraySAIS {
      vector<int> sa, lcp, rank;
      SparseTable<int> rmq;
      SuffixArraySAIS() {}
      SuffixArraySAIS(string str_) : str(str_) {
            init(str_);
      }
      SuffixArraySAIS(const vector<int>& S_, int A_SIZE_, bool lcp_flag = true) : S(S_), A_SIZE(A_SIZE_) {
            buildSA();
            if (lcp_flag) {
                  buildLCP();
                  buildRMQ();
            }
      }
      void init(string str_) {
            str = str_;
            N = str.size() + 1;
            S = vector<int>(N, 0);
            for (int i = 0; i < N; i++) S[i] = str[i];
            A_SIZE = 256;

            buildSA();
            buildLCP();
            buildRMQ();
      }
      string str;
      vector<int> S;
      int A_SIZE;
      int N;
      vector<int> t, B;
      enum { STYPE, LTYPE };

      inline bool is_lms(int i) {
            return i > 0 && t[i] == STYPE && t[i - 1] == LTYPE;
      }
      void bucket() {
            B = vector<int>(A_SIZE);
            for (int i = 0; i < N; i++) B[S[i]]++;
            for (int i = 0; i < A_SIZE - 1; i++) B[i + 1] += B[i];
      }
      void induced_sort() {
            bucket();
            for (int i = 0; i < N; i++) {
                  int j = sa[i] - 1;
                  if (j >= 0 && S[j] >= S[j + 1]) sa[B[S[j] - 1]++] = j;
            }
            bucket();
            for (int i = N; i--; ) {
                  int j = sa[i] - 1;
                  if (j >= 0 && S[j] <= S[j + 1]) sa[--B[S[j]]] = j;
            }
      }
      void buildSA() {
            N = S.size();
            sa.assign(N, -1);
            if (N == 1) {
                  sa[0] = 0;
                  return;
            }
            t.assign(N, STYPE);
            for (int i = N - 1; i--;)
                  if (S[i] > S[i + 1] || (S[i] == S[i + 1] && t[i + 1] == LTYPE))
                        t[i] = LTYPE;
            bucket();
            for (int i = N; i--;)
                  if (is_lms(i)) sa[--B[S[i]]] = i;
            induced_sort();

            int N1 = 0;
            for (int i = 0; i < N; i++) if (is_lms(sa[i])) sa[N1++] = sa[i];

            fill(sa.begin() + N1, sa.end(), -1);
            int name = 0, prev = -1;
            for (int i = 0; i < N1; i++) {
                  int cur = sa[i];
                  bool diff = (prev == -1);
                  for (int j = 0; !diff; j++) {
                        if (j > 0 && is_lms(cur + j)) break;
                        if (S[cur + j] != S[prev + j]) diff = true;
                  }
                  if (diff) name++;
                  sa[N1 + cur / 2] = name - 1;
                  prev = cur;
            }
            vector<int> S1, sa1(N1);
            for (int i = N1; i < N; i++) if (sa[i] >= 0) S1.push_back(sa[i]);
            if (name == N1) for (int i = 0; i < N1; i++) sa1[S1[i]] = i;
            else sa1 = SuffixArraySAIS(S1, name, false).sa;

            N1 = 0;
            for (int i = 0; i < N; i++) if (is_lms(i)) S1[N1++] = i;
            for (int i = 0; i < N1; i++) sa1[i] = S1[sa1[i]];

            fill(sa.begin(), sa.end(), -1);
            bucket();
            for (int i = N1; i--;) {
                  int j = sa1[i];
                  sa[--B[S[j]]] = j;
            }
            induced_sort();
      }
      void buildLCP() {
            rank.resize(N);
            lcp.resize(N - 1);
            for (int i = 0; i < N; i++) rank[sa[i]] = i;
            int h = 0;
            for (int i = 0; i < N - 1; i++) {
                  int j = sa[rank[i] - 1];
                  if (h > 0) h--;
                  for (; j + h < N && i + h < N && S[j + h] == S[i + h]; h++);
                  lcp[rank[i] - 1] = h;
            }
      }

      void buildRMQ() {
            rmq.init(lcp);
      }
      int common_prefix(int x, int y) {//xからとyからどこまでprefixが一緒か（後ろ削る）
            if (x == y) return N - 1 - x;
            if (y >= N - 1) return 0;
            if (rank[x] > rank[y]) swap(x, y);
            return rmq.get(rank[x], rank[y]);
      }
      int compare(int x, int xn, int y, int yn) {//xとｙn文字の関係
            int l = common_prefix(x, y);
            if (l >= xn || l >= yn) return xn < yn ? -1 : xn == yn ? 0 : 1;
            return rank[x] < rank[y] ? -1 : x == y ? 0 : 1;
      }
};


int contain_count (string S, vector<int> &sa, string T) {
      int a = 0; int b = S.length()  +1;
      while (b - a > 1) {
            int c = (a + b) / 2;
            if (S.compare(sa[c], T.length(), T) < 0) a = c;
            else b = c; 
      }
      if (b == S.length() + 1 || S.compare(sa[b], T.length(), T) != 0) return 0;
      int ret = b;

      a = 0;  b = S.length() + 1;
      while (b - a > 1) {
            int c = (a + b) / 2;
            if (S.compare(sa[c], T.length(), T) <= 0) a = c;
            else b = c; 
      }

      
      
      return b - ret;

}//文字列腸をLろするとsuffixarrayのサイズはL+1!!!!!!!!!!!

signed main() {
      ios::sync_with_stdio(false);
      cin.tie(0);

      string s;
      cin >> s;
      int M; 
      cin >> M;
      SuffixArraySAIS SAIS(s);
    //  for (int i = 0; i <= s.size(); i++) cout << s.substr(SAIS.sa[i], s.size() - SAIS.sa[i]) << endl;
      int ans = 0;
      for (int i = 0; i < M; i++) {
            string c;
            cin >> c;
            int n = c.size();
            ans += contain_count(s, SAIS.sa, c);          
      }

      cout << ans << endl;
}
0