結果

問題 No.430 文字列検索
コンテスト
ユーザー kimiyuki
提出日時 2016-10-18 17:21:33
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,312 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 523 ms
コンパイル使用メモリ 76,520 KB
最終ジャッジ日時 2026-05-09 08:56:32
合計ジャッジ時間 2,370 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:13:5: error: 'uint64_t' was not declared in this scope
   13 |     uint64_t pow_p[limit]; pow_p[0] = 1; repeat (i, limit-1) pow_p[i+1] = pow_p[i] * p;
      |     ^~~~~~~~
main.cpp:5:1: note: 'uint64_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    4 | #include <utility>
  +++ |+#include <cstdint>
    5 | #define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
main.cpp:13:28: error: 'pow_p' was not declared in this scope
   13 |     uint64_t pow_p[limit]; pow_p[0] = 1; repeat (i, limit-1) pow_p[i+1] = pow_p[i] * p;
      |                            ^~~~~
main.cpp:14:13: error: expected ';' before 'pow_q'
   14 |     uint64_t pow_q[limit]; pow_q[0] = 1; repeat (i, limit-1) pow_q[i+1] = pow_q[i] * q;
      |             ^~~~~~
      |             ;
main.cpp:14:28: error: 'pow_q' was not declared in this scope
   14 |     uint64_t pow_q[limit]; pow_q[0] = 1; repeat (i, limit-1) pow_q[i+1] = pow_q[i] * q;
      |                            ^~~~~
main.cpp:21:37: error: template argument 1 is invalid
   21 |         set<pair<uint64_t,uint64_t> > hashes;
      |                                     ^
main.cpp:21:37: error: template argument 2 is invalid
main.cpp:21:37: error: template argument 3 is invalid
main.cpp:23:21: error: expected ';' before 'hp'
   23 |             uint64_t hp = 0, hq = 0;
      |                     ^~~
      |                     ;
main.cpp:25:17: error: 'hp' was not declared in this scope; did you mean 'p'?
   25 |                 hp = hp * p + a;
      |                 ^~
      |                 p
main.cpp:26:17: error: 'hq' was not declared in this scope; did you mean 'q'?
   26 |                 hq = hq * q + a;
      |                 ^~
      |                 q
main.cpp:28:20: error: request for member 'emplace' in 'hashes', which is of non-class type 'int'
   28 |             hashes.emplace(hp, hq);
      |                    ^~~~~~~
main.cpp:28:28

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <set>
#include <utility>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i))
using namespace std;
int main() {
    // prepare
    const int limit = 10;
    const int p = 1e9+7;
    const int q = 1e9+9;
    uint64_t pow_p[limit]; pow_p[0] = 1; repeat (i, limit-1) pow_p[i+1] = pow_p[i] * p;
    uint64_t pow_q[limit]; pow_q[0] = 1; repeat (i, limit-1) pow_q[i+1] = pow_q[i] * q;
    // input
    string s; int n; cin >> s >> n;
    vector<string> cs(n); repeat (i,n) cin >> cs[i];
    // compute
    int ans = 0;
    repeat_from (len, 1, limit+1) {
        set<pair<uint64_t,uint64_t> > hashes;
        for (string c : cs) if (c.length() == len) {
            uint64_t hp = 0, hq = 0;
            for (char a : c) {
                hp = hp * p + a;
                hq = hq * q + a;
            }
            hashes.emplace(hp, hq);
        }
        uint64_t hp = 0, hq = 0;
        repeat (i, (int)s.length()) {
            char c = i - len >= 0 ? s[i - len] : 0;
            hp = (hp - c * pow_p[len-1]) * p + s[i];
            hq = (hq - c * pow_q[len-1]) * q + s[i];
            if (hashes.count(make_pair(hp, hq))) ans += 1;
        }
    }
    // output
    cout << ans << endl;
    return 0;
}
0