結果
問題 | No.430 文字列検索 |
ユーザー |
|
提出日時 | 2016-10-02 23:50:01 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,621 bytes |
コンパイル時間 | 625 ms |
コンパイル使用メモリ | 68,700 KB |
実行使用メモリ | 20,992 KB |
最終ジャッジ日時 | 2024-11-10 00:05:01 |
合計ジャッジ時間 | 2,059 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 13 WA * 1 |
ソースコード
#include<iostream>#include<map>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];}}void work() {map<int, int> hash2cnt;for (int len = 1; len <= min(10, (int) txt.size()); ++len) {int currHash = 0;for (int i = 0; i < len; ++i) {currHash = add(mul(currHash, 256), txt[i]);}int p = 1;for (int i = 0; i < len - 1; ++i) {p = mul(p, 256);}for (int i = 0; i + len <= txt.size(); ++i) {if (hash2cnt.count(currHash)) {int old = hash2cnt[currHash];hash2cnt[currHash] = old + 1;}else {hash2cnt[currHash] = 1;}currHash = sub(currHash, mul(p, txt[i]));currHash = mul(currHash, 256);currHash = add(currHash, txt[i + len]);}}int sum = 0;for (int i = 0; i < nWord; ++i) {int targetHash = 0;for (int j = 0; j < word[i].size(); ++j) {targetHash = add(mul(targetHash, 256), word[i][j]);}sum += hash2cnt[targetHash];}cout << sum << endl;}int main() {read();work();return 0;}