結果
問題 | No.430 文字列検索 |
ユーザー |
|
提出日時 | 2016-10-02 23:15:01 |
言語 | C++11 (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,386 bytes |
コンパイル時間 | 479 ms |
コンパイル使用メモリ | 56,052 KB |
実行使用メモリ | 8,704 KB |
最終ジャッジ日時 | 2024-11-10 00:03:17 |
合計ジャッジ時間 | 3,750 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 4 |
other | AC * 1 TLE * 1 -- * 12 |
ソースコード
#include<iostream>using namespace std;const int MOD = 1000000007;const int WORD = 5005;int add(int a, int b) {return (1LL * a + b) % MOD;}int sub(int a, int b) {a %= MOD;b %= MOD;return (a + MOD - b) % MOD;}int mul(int a, int b) {return (1LL * a * b) % MOD;}string txt;int nWord;string word[WORD];void read() {cin >> txt;cin >> nWord;for (int i = 0; i < nWord; ++i) {cin >> word[i];}}int calc(string &wd) {if (txt.size() < wd.size()) return 0;int targetHash = 0;for (int i = 0; i < wd.size(); ++i) {targetHash = add(mul(targetHash, 256), wd[i]);}int currHash = 0;for (int i = 0; i < wd.size(); ++i) {currHash = add(mul(currHash, 256), txt[i]);}int p = 1;for (int i = 0; i < wd.size() - 1; ++i) {p = mul(p, 256);}int cnt = 0;for (int i = 0; i + wd.size() <= txt.size(); ++i) {if (currHash == targetHash) {++cnt;}currHash = sub(currHash, mul(p, txt[i]));currHash = mul(currHash, 256);currHash = add(currHash, txt[i + wd.size()]);}return cnt;}void work() {int sum = 0;for (int i = 0; i < nWord; ++i) {sum += calc(word[i]);}cout << sum << endl;}int main() {read();work();return 0;}