結果

問題 No.430 文字列検索
コンテスト
ユーザー ei1333333
提出日時 2016-10-02 22:57:43
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 76 ms / 2,000 ms
コード長 2,161 bytes
コンパイル時間 1,259 ms
コンパイル使用メモリ 166,508 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-10 00:02:42
合計ジャッジ時間 2,476 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long hash_type;

struct RollingHash
{
  hash_type base1;
  vector< hash_type > hash1, pow1;

  RollingHash() : base1(29LL)
  {
  }

  void init(const string& s)
  {
    int n = s.size();
    hash1.assign(n + 1, 0);
    pow1.assign(n + 1, 1);
    for(int i = 0; i < n; i++) {
      hash1[i + 1] = (hash1[i] + s[i] - 'A') * base1;
      pow1[i + 1] = pow1[i] * base1;
    }
  }

  hash_type get(int l, int r)
  {
    if(r >= hash1.size()) return (~0);
    return ((hash1[r] - hash1[l] * pow1[r - l]));
  }

};

RollingHash hashed;
int N, M;
string S;

bool compare(const int& a, const int& b)
{
  int low = 0, high = min(N - a, N - b) + 1;
  while(high - low > 1) {
    int mid = (low + high) >> 1;
    if(hashed.get(a, a + mid) == hashed.get(b, b + mid)) low = mid;
    else high = mid;
  }
  if(low == min(N - a, N - b)) return (low == N - a);
  return (S[a + low] < S[b + low]);
}

string T;

bool comp(RollingHash& hashed1, const int& b)
{
  int mm = hashed1.hash1.size() - 1;
  int low = 0, high = min(mm, N - b) + 1;
  while(high - low > 1) {
    int mid = (low + high) >> 1;
    if(hashed1.get(0, mid) == hashed.get(b, b + mid)) low = mid;
    else high = mid;
  }
  if(low == min(mm, N - b)) return (low == mm);
  return (T[low] < S[b + low]);
}

int main()
{
  cin >> S;
  N = S.size();
  hashed.init(S);
  vector< int > idx(S.size());
  iota(idx.begin(), idx.end(), 0);
  sort(idx.begin(), idx.end(), compare);
  int M;
  cin >> M;

  long long ret = 0;
  while(M--) {
    cin >> T;
    RollingHash buff;
    buff.init(T);
    hash_type val = buff.get(0, T.size());
    int low1 = -1, high1 = S.size() - 1;
    while(high1 - low1 > 1) {
      int mid = (low1 + high1) >> 1;
      if(comp(buff, idx[mid])) high1 = mid;
      else low1 = mid;
    }
    if(val != hashed.get(idx[high1], idx[high1] + T.size())) continue;
    int low2 = high1, high2 = S.size();
    while(high2 - low2 > 1) {
      int mid = (low2 + high2) >> 1;
      if(val == hashed.get(idx[mid], idx[mid] + T.size())) low2 = mid;
      else high2 = mid;
    }
    ret += low2 - high1 + 1;
  }
  cout << ret << endl;
}
0