結果

問題 No.430 文字列検索
ユーザー tnakao0123tnakao0123
提出日時 2016-10-06 12:11:56
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 5,967 bytes
コンパイル時間 783 ms
コンパイル使用メモリ 94,524 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-10 00:09:53
合計ジャッジ時間 1,459 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 10 ms
5,248 KB
testcase_02 AC 9 ms
5,248 KB
testcase_03 AC 7 ms
5,248 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 1 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 7 ms
5,248 KB
testcase_09 AC 1 ms
5,248 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 12 ms
5,248 KB
testcase_12 AC 12 ms
5,248 KB
testcase_13 AC 11 ms
5,248 KB
testcase_14 AC 12 ms
5,248 KB
testcase_15 AC 11 ms
5,248 KB
testcase_16 AC 8 ms
5,248 KB
testcase_17 AC 7 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 430.cc: No.430 文字列検索 - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

typedef vector<int> vi;
typedef unsigned char uchar;
typedef vector<uchar> vuc;

// global variables

// subroutines

inline uchar mask(int i) { return (uchar)(1 << (7 - i)); }

inline bool tget(vuc &t, int i) {
  return (t[i / 8] & mask(i % 8)) ? true : false;
}

inline void tset(vuc &t, int i, bool b) {
  if (b) t[i / 8] |= mask(i % 8);
  else   t[i / 8] &= ~mask(i % 8);
}

inline bool isLMS(vuc &t, int i) {
  return (i > 0 && tget(t, i) && ! tget(t, i - 1));
}

// find the start or end of each bucket
void getBuckets(int *s, vi &bkt, int n, int k, bool end) {
  // clear all buckets
  bkt.assign(k, 0);

  // compute the size of each bucket
  for (int i = 0; i < n; i++) bkt[s[i]]++;

  for (int i = 0, sum = 0; i < k; i++) {
    sum += bkt[i];
    bkt[i] = end ? sum : sum - bkt[i];
  }
}

// compute SAl
void induceSAl(vuc &t, int *SA, int *s, vi &bkt, int n, int k, bool end) {
  // find starts of buckets
  getBuckets(s, bkt, n, k, end);

  for (int i = 0; i < n; i++) {
    int j = SA[i] - 1;
    if (j >= 0 && ! tget(t, j)) SA[bkt[s[j]]++] = j;
  }
}

// compute SAs
void induceSAs(vuc &t, int *SA, int *s, vi &bkt, int n, int k, bool end) {
  // find ends of buckets
  getBuckets(s, bkt, n, k, end);

  for (int i = n - 1; i >= 0; i--) {
    int j = SA[i] - 1;
    if (j >= 0 && tget(t, j)) SA[--bkt[s[j]]] = j;
  }
}

// find the suffix array SA of s[0..n-1] in {1..K}
// require s[n-1]=0 (the sentinel!), n>=2
// use a working space (excluding s and SA) of
// at most 2.25n+O(1) for a constant alphabet

void SA_IS(int *s, int *SA, int n, int k) {
  // LS-type array in bits
  vuc t(n / 8 + 1);

  // classify the type of each character
  // the sentinel must be in s1, important!!!
  tset(t, n - 1, true);
  tset(t, n - 2, false);
  for (int i = n - 3; i >= 0; i--)
    if (s[i] < s[i + 1] || (s[i] == s[i + 1] && tget(t, i + 1)))
      tset(t, i, true);

  // stage 1: reduce the problem by at least 1/2
  // sort all the S-substrings
  // bucket array
  vi bkt(k);

  // find ends of buckets
  getBuckets(s, bkt, n, k, true);
  for (int i = 0; i < n; i++) SA[i] = -1;
  for (int i = 1; i < n; i++)
    if (isLMS(t, i)) SA[--bkt[s[i]]] = i;
  
  induceSAl(t, SA, s, bkt, n, k, false);
  induceSAs(t, SA, s, bkt, n, k, true);

  // compact all the sorted substrings into
  // the first n1 items of SA
  // 2*n1 must be not larger than n (proveable)
  int n1 = 0;
  for (int i = 0; i < n; i++)
    if (isLMS(t, SA[i])) SA[n1++] = SA[i];

  // find the lexicographic names of substrings
  // init the name array buffer
  for (int i = n1; i < n; i++) SA[i] = -1;

  int name = 0, prev = -1;
  for (int i = 0; i < n1; i++) {
    int pos = SA[i];
    bool diff = false;
    for (int d = 0; d < n; d++) {
      if (prev == -1 || s[pos + d] != s[prev + d] ||
	  tget(t, pos + d) != tget(t, prev + d)) {
	diff = true;
	break;
      }
      else if (d > 0 && (isLMS(t, pos + d) || isLMS(t, prev + d)))
	break;
    }
    if (diff) name++, prev = pos;

    pos /= 2;
    SA[n1 + pos] = name - 1;
  }

  for (int i = n - 1, j = n - 1; i >= n1; i--)
    if (SA[i] >= 0) SA[j--] = SA[i];

  // stage 2: solve the reduced problem
  // recurse if names are not yet unique
  int *SA1 = SA, *s1 = SA + n - n1;
  if (name < n1)
    SA_IS(s1, SA1, n1, name);
  else // generate the suffix array of s1 directly
    for (int i = 0; i < n1; i++) SA1[s1[i]] = i;

  // stage 3: induce the result for
  // the original problem
  // bucket array
  bkt.assign(k, 0);
  // put all the LMS characters into their buckets
  // find ends of buckets
  getBuckets(s, bkt, n, k, true);

  for (int i = 1, j = 0; i < n; i++)
    if (isLMS(t, i)) s1[j++] = i; // get p1

  // get index in s
  for (int i = 0; i < n1; i++) SA1[i] = s1[SA1[i]];

  // init SA[n1..n-1]
  for (int i = n1; i < n; i++) SA[i] = -1;
  for (int i = n1 - 1; i >= 0; i--) {
    int j=SA[i];
    SA[i] = -1;
    SA[--bkt[s[j]]] = j;
  }

  induceSAl(t, SA, s, bkt, n, k, false);
  induceSAs(t, SA, s, bkt, n, k, true);
}

void SA_IS(string &s, vi &SA, int k = 256) {
  int n = s.size();
  int *buf0 = new int[n + 1], *buf1 = new int[n + 1];
  
  for (int i = 0; i < n; i++) buf0[i] = s[i];
  buf0[n] = 0;
  SA_IS(buf0, buf1, n + 1, k);

  SA.resize(n + 1);
  for (int i = 0; i <= n; i++) SA[i] = buf1[i];
}

void LCP(string &s, vi &sa, vi &lcp) {
  int n = s.size();
  lcp.resize(n + 1);
  vi rank_(n + 1);
  for (int i = 0; i <= n; i++) rank_[sa[i]] = i;

  int h = 0;
  lcp[0] = 0;
  for (int i = 0; i < n; i++) {
    int j = sa[rank_[i] - 1];
    if (h > 0) h--;
    for (; j + h < n && i + h < n; h++)
      if (s[j + h] != s[i + h]) break;
    lcp[rank_[i]] = h;
  }
}

bool lt_substr(string &s, string &t, int si = 0, int ti = 0) {
  int sn = s.size(), tn = t.size();
  while (si < sn && ti < tn) {
    if (s[si] < t[ti]) return true;
    if (s[si] > t[ti]) return false;
    si++, ti++;
  }
  return (si >= sn && ti < tn);
}

int sa_lb(string &s, vi &SA, string &t) {
  int i0 = -1;
  int i1 = SA.size();

  while (i0 + 1 < i1) {
    int im = (i0 + i1) / 2;
    if (lt_substr(s, t, SA[im])) i0 = im;
    else i1 = im;
  }
  return i1;
}

/* main */

int main() {
  string s;
  cin >> s;

  vi SA, lcp;
  SA_IS(s, SA);
  LCP(s, SA, lcp);
  //for (int i = 0; i < SA.size(); i++) printf("%d %d\n", SA[i], lcp[i]);

  int m;
  cin >> m;
  int sum = 0;

  while (m--) {
    string t;
    cin >> t;

    int i0 = sa_lb(s, SA, t);
    t.back()++;
    int i1 = sa_lb(s, SA, t);
    sum += i1 - i0;
    //printf("%d %d\n", i0, i1);
  }

  printf("%d\n", sum);
  return 0;
}
0