結果
| 問題 | No.430 文字列検索 |
| ユーザー |
👑  jupiro
|
| 提出日時 | 2019-08-15 17:30:48 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,455 bytes |
| コンパイル時間 | 1,628 ms |
| コンパイル使用メモリ | 97,116 KB |
| 実行使用メモリ | 9,548 KB |
| 最終ジャッジ日時 | 2023-10-19 19:12:30 |
| 合計ジャッジ時間 | 5,105 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
8,696 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 <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <fstream>
#include <bitset>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const long long MOD = 1000000007LL;
const long long MAX = 500000LL;
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
class RollingHash {
public:
typedef long long int_type;
typedef pair<int_type, int_type> hash_type;
int_type base1;
int_type base2;
int_type mod1;
int_type mod2;
vector<int_type> hash1;
vector<int_type> hash2;
vector<int_type> pow1;
vector<int_type> pow2;
RollingHash() : base1(1009), base2(1007), mod1(1000000007), mod2(1000000009) {}
void init(const string &s) {
ll n = s.size();
hash1.assign(n + 1, 0);
hash2.assign(n + 1, 0);
pow1.assign(n + 1, 1);
pow2.assign(n + 1, 1);
for (ll i = 0; i < n; i++) {
hash1[i + 1] = (hash1[i] * base1 + s[i]) % mod1;
hash2[i + 1] = (hash2[i] * base2 + s[i]) % mod2;
pow1[i + 1] = pow1[i] * base1 % mod1;
pow2[i + 1] = pow2[i] * base2 % mod2;
}
}
hash_type get(ll l, ll r) {
int_type t1 = ((hash1[r] - hash1[l] * pow1[r - l]) % mod1 + mod1) % mod1;
int_type t2 = ((hash2[r] - hash2[l] * pow2[r - l]) % mod2 + mod2) % mod2;
return make_pair(t1, t2);
}
void add(string &t) {
ll old_len = hash1.size();
hash1.resize(old_len + t.size());
hash2.resize(old_len + t.size());
pow1.resize(hash1.size());
pow2.resize(hash1.size());
for (ll i = 0; i < t.size(); i++) {
hash1[old_len + i] = (hash1[old_len + i - 1] * base1 + t[i]) % mod1;
hash2[old_len + i] = (hash2[old_len + i - 1] * base2 + t[i]) % mod2;
pow1[old_len + i] = pow1[old_len + i - 1] * base1 % mod1;
pow2[old_len + i] = pow2[old_len + i - 1] * base2 % mod2;
}
}
};
int main()
{
string s;
cin >> s;
RollingHash rol1;
rol1.init(s);
ll M;
cin >> M;
ll cnt = 0;
for (ll i = 0; i < M; i++) {
string c;
cin >> c;
RollingHash rol2;
rol2.init(c);
for (ll j = 0; j <= (ll)s.size() - (ll)c.size(); j++) {
if (rol1.get(j, j + c.size()) == rol2.get(0, c.size())) {
cnt++;
}
}
}
cout << cnt << endl;
return 0;
}