結果
問題 | No.430 文字列検索 |
ユーザー | kappybar |
提出日時 | 2020-07-19 13:02:09 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 286 ms / 2,000 ms |
コード長 | 2,024 bytes |
コンパイル時間 | 1,943 ms |
コンパイル使用メモリ | 179,020 KB |
実行使用メモリ | 27,904 KB |
最終ジャッジ日時 | 2024-11-10 00:45:08 |
合計ジャッジ時間 | 3,096 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 269 ms
27,904 KB |
testcase_02 | AC | 27 ms
6,820 KB |
testcase_03 | AC | 28 ms
6,816 KB |
testcase_04 | AC | 1 ms
6,816 KB |
testcase_05 | AC | 1 ms
6,816 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 286 ms
27,648 KB |
testcase_09 | AC | 3 ms
6,820 KB |
testcase_10 | AC | 16 ms
6,820 KB |
testcase_11 | AC | 75 ms
8,832 KB |
testcase_12 | AC | 76 ms
8,832 KB |
testcase_13 | AC | 75 ms
8,960 KB |
testcase_14 | AC | 67 ms
7,296 KB |
testcase_15 | AC | 54 ms
6,820 KB |
testcase_16 | AC | 32 ms
6,816 KB |
testcase_17 | AC | 31 ms
6,816 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) using namespace std; using ll = long long ; using P = pair<int,int> ; using pll = pair<long long,long long>; constexpr int INF = 1e9; constexpr long long LINF = 1e17; constexpr int MOD = 1000000007; constexpr double PI = 3.14159265358979323846; struct Rollinghash{ string S; int n; vector<unsigned long long int> powb1; vector<unsigned long long int> powb2; vector<unsigned long long int> H1; vector<unsigned long long int> H2; unsigned long long int B1 = 1000007; unsigned long long int B2 = 1000009; unsigned long long int M1 = 1000000007; unsigned long long int M2 = 1000000009; Rollinghash(string S):S(S){ n=(int)(S.size()); H1.resize(n+1); H2.resize(n+1); powb1.resize(n+1); powb2.resize(n+1); init(); } void init(){ unsigned long long int p1 = 1; unsigned long long int p2 = 1; powb1[0] = p1; powb2[0] = p2; H1[0] = 0; H2[0] = 0; for(int i=1;i<=n;i++){ powb1[i] = (powb1[i-1]*B1)%M1; powb2[i] = (powb2[i-1]*B2)%M2; } for(int i=1;i<=n;i++){ H1[i] = (H1[i-1]*B1 + S[i-1])%M1; H2[i] = (H2[i-1]*B2 + S[i-1])%M2; } } //[l,r) pair<unsigned long long int,unsigned long long int> hash(int l,int r){ return make_pair( (H1[r] - (H1[l] * powb1[r-l])%M1 + M1)%M1,(H2[r] - (H2[l] * powb2[r-l])%M2 + M2)%M2 ); } }; int main(){ string S; cin >> S; Rollinghash Rs(S); map<pair<unsigned long long int,unsigned long long int>,long long int> mp; for(int i=1;i<=min(10,(int)(S.size()));i++){ for(int j=0;j+i<=S.size();j++){ mp[Rs.hash(j,j+i)] ++; } } ll ans = 0; int m; cin >> m; rep(i,m){ string C; cin >> C; Rollinghash Rc(C); ans += mp[Rc.hash(0,C.size())]; } cout << ans << endl; return 0; }