結果
問題 | No.430 文字列検索 |
ユーザー | akusyounin2412 |
提出日時 | 2018-08-19 22:58:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 4,528 bytes |
コンパイル時間 | 1,443 ms |
コンパイル使用メモリ | 133,008 KB |
実行使用メモリ | 9,216 KB |
最終ジャッジ日時 | 2024-11-10 00:19:35 |
合計ジャッジ時間 | 2,951 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
8,704 KB |
testcase_01 | AC | 101 ms
9,216 KB |
testcase_02 | AC | 60 ms
9,216 KB |
testcase_03 | AC | 70 ms
9,088 KB |
testcase_04 | AC | 4 ms
8,576 KB |
testcase_05 | AC | 3 ms
8,576 KB |
testcase_06 | AC | 3 ms
8,448 KB |
testcase_07 | AC | 3 ms
8,576 KB |
testcase_08 | AC | 90 ms
9,088 KB |
testcase_09 | AC | 5 ms
8,576 KB |
testcase_10 | AC | 9 ms
8,704 KB |
testcase_11 | AC | 103 ms
9,088 KB |
testcase_12 | AC | 101 ms
9,088 KB |
testcase_13 | AC | 101 ms
9,088 KB |
testcase_14 | AC | 101 ms
9,216 KB |
testcase_15 | AC | 98 ms
9,216 KB |
testcase_16 | AC | 96 ms
9,088 KB |
testcase_17 | AC | 94 ms
9,216 KB |
ソースコード
# include <iostream> # include <algorithm> #include <array> # include <cassert> #include <cctype> #include <climits> #include <numeric> # include <vector> # include <string> # include <set> # include <map> # include <cmath> # include <iomanip> # include <functional> # include <tuple> # include <utility> # include <stack> # include <queue> # include <list> # include <bitset> # include <complex> # include <chrono> # include <random> # include <limits.h> # include <unordered_map> # include <unordered_set> # include <deque> # include <cstdio> # include <cstring> #include <stdio.h> #include<time.h> #include <stdlib.h> #include <cstdint> #include <cfenv> //#include <bits/stdc++.h> using namespace std; using LL = int; using ULL = unsigned long long; long long MOD = 1000000000 + 7; constexpr long long INF = numeric_limits<LL>::max(); const double PI = acos(-1); #define fir first #define sec second #define thi third #define debug(x) cerr<<#x<<": "<<x<<'\n' typedef pair<LL, LL> Pll; typedef pair<LL, pair<LL, LL>> Ppll; typedef pair<LL, pair<LL, bitset<100001>>> Pbll; typedef pair<LL, pair<LL, vector<LL>>> Pvll; typedef pair<LL, LL> Vec2; struct Tll { LL first, second, third; }; struct Fll { LL first, second, third, fourd; }; typedef pair<LL, Tll> Ptll; #define rep(i,rept) for(LL i=0;i<rept;i++) #define Mfor(i,mf) for(LL i=mf-1;i>=0;i--) LL h, w, n, m, k, t, s, q, last, cnt, sum, ans, dp[10000], a[2000000], b[2000000]; string str, ss; bool f[1100][1100]; char c; int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } }; struct Edge { LL to, cost; }; vector<Edge>vec[200000]; list<LL>li[20000]; vector<LL>v; map<string, vector<LL>>ma; multiset<LL>st[3]; void YN(bool f) { if (f) cout << "YES" << endl; else cout << "NO" << endl; } void yn(bool f) { if (f) cout << "Yes" << endl; else cout << "No" << endl; } const int _base = 1e9 + 7; struct RollingHash { string former; int sz; vector< unsigned > hashed, power; vector<int>idx; RollingHash(const string& s) { //文字列sのハッシュテーブルを構築する former = s; sz = s.size(); idx.resize(sz); hashed.assign(sz + 1, 0); power.assign(sz + 1, 0); power[0] = 1; for (int i = 0; i < sz; i++) { power[i + 1] = power[i] * _base; } for (int i = 0; i < sz; i++) { hashed[i + 1] = (hashed[i] + s[i]) * _base; } iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](const int& a, const int& b) { int low = 0, high = min(sz - a, sz - b) + 1; while (high - low > 1) { int mid = (low + high) >> 1; if (get(a, a + mid) == get(b, b + mid)) low = mid; else high = mid; } if (low == min(sz - a, sz - b)) return (low == sz - a); return (former[a + low] < former[b + low]); }); } bool comp(RollingHash& hashed1, const int& b) { int mm = hashed1.hashed.size() - 1; int low = 0, high = min(mm, sz - b) + 1; while (high - low > 1) { int mid = (low + high) >> 1; if (hashed1.get(0, mid) == get(b, b + mid)) low = mid; else high = mid; } if (low == min(mm, sz - b)) return (low == mm); return (hashed1.former[low] < former[b + low]); } unsigned get(int l, int r) { //区間[l,r)のハッシュ値を求める return((hashed[r] - hashed[l] * power[r - l])); } unsigned connect(int h1, int h2, int h2len) { //ハッシュ値h1と長さh2lenのハッシュ値h2を結合する return(h1 * power[h2len] + h2); } int LCP(RollingHash& b, int l1, int r1, int l2, int r2) { //区間[l1,r1)とハッシュテーブルがbからなる区間[l2,r2)の文字列の最長共通接頭辞の長さを求める int len = min(r1 - l1, r2 - l2); int low = -1, high = len + 1; while (high - low > 1) { int mid = (low + high) >> 1; if (get(l1, l1 + mid) == b.get(l2, l2 + mid)) low = mid; else high = mid; } return(low); } int contain(RollingHash& b) { unsigned val = b.get(0, b.former.size()); int low1 = -1, high1 = former.size() - 1; while (high1 - low1 > 1) { int mid = (low1 + high1) >> 1; if (comp(b, idx[mid])) high1 = mid; else low1 = mid; } if (val != get(idx[high1], idx[high1] + b.former.size())) return 0; int low2 = high1, high2 = former.size(); while (high2 - low2 > 1) { int mid = (low2 + high2) >> 1; if (val == get(idx[mid], idx[mid] + b.former.size())) low2 = mid; else high2 = mid; } return low2 - high1 + 1; } }; int main() { cin >> str; RollingHash cur(str); cin >> n; rep(i, n) { cin >> ss; RollingHash nex(ss); ans+=cur.contain(nex); } cout << ans << endl; return 0; }