結果
| 問題 | No.430 文字列検索 |
| ユーザー |
 Vi24E
|
| 提出日時 | 2022-07-10 18:06:20 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,139 bytes |
| コンパイル時間 | 1,386 ms |
| コンパイル使用メモリ | 166,308 KB |
| 実行使用メモリ | 8,760 KB |
| 最終ジャッジ日時 | 2023-09-02 01:21:26 |
| 合計ジャッジ時間 | 5,060 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
7,752 KB |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
ソースコード
#include<bits/stdc++.h>
using namespace std;
//aの中からbに合致するものの最初のindexのvectorを返す
int rolling_hash(string &a, string &b){
using lll = __int128_t;
const lll base = 591591593, mod = (1ll<<61) - 1;
lll basem = 1;
int n = a.size(), m = b.size();
lll t = m, u = base;
t--;
while (t) {
if (t & 1) basem = (basem * u) % mod;
u = (u * u) % mod;
t >>= 1;
}
lll hash_a = 0, hash_b = 0;
for (auto x : b){
hash_b *= base;
hash_b += (lll)(x) + 127;
hash_b %= mod;
}
for (int i = 0; i < m; i++){
hash_a *= base;
hash_a += (lll)(a[i]) + 127;
hash_a %= mod;
}
int pos = 0;
if (hash_a == hash_b) pos++;
for (int i = 0; i < n - m; i++){
hash_a -= basem * ((lll)(a[i]) + 127);
hash_a *= base;
hash_a += ((lll)(a[i + m]) + 127) + mod;
hash_a = ((hash_a % mod) + mod) % mod;
if (hash_a == hash_b) pos++;
}
return pos;
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
string s;
cin >> s;
int m;
cin >> m;
int ans = 0;
for (int i = 0; i < m; i++){
string c;
cin >> c;
ans += rolling_hash(s, c);
}
cout << ans << endl;
}