結果

問題 No.430 文字列検索
コンテスト
ユーザー KoD
提出日時 2020-04-06 14:18:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,198 bytes
コンパイル時間 573 ms
コンパイル使用メモリ 71,616 KB
最終ジャッジ日時 2025-01-09 14:31:32
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:114:8: error: ‘unordered_map’ is not a member of ‘std’
  114 |   std::unordered_map<unsigned long long, int> map;
      |        ^~~~~~~~~~~~~
main.cpp:10:1: note: ‘std::unordered_map’ is defined in header ‘<unordered_map>’; did you forget to ‘#include <unordered_map>’?
    9 | #include <map>
  +++ |+#include <unordered_map>
   10 | 
main.cpp:114:22: error: expected primary-expression before ‘unsigned’
  114 |   std::unordered_map<unsigned long long, int> map;
      |                      ^~~~~~~~
main.cpp:118:5: error: ‘map’ was not declared in this scope
  118 |     map[rolling_hash(C).hash(0, C.size())]++;
      |     ^~~
main.cpp:118:5: note: suggested alternatives:
In file included from /usr/include/c++/13/map:63,
                 from main.cpp:9:
/usr/include/c++/13/bits/stl_map.h:102:11: note:   ‘std::map’
  102 |     class map
      |           ^~~
/usr/include/c++/13/map:80:13: note:   ‘std::pmr::map’
   80 |       using map
      |             ^~~
main.cpp:124:14: error: ‘map’ was not declared in this scope
  124 |       ans += map[hash.hash(i, i + len)];
      |              ^~~
main.cpp:124:14: note: suggested alternatives:
/usr/include/c++/13/bits/stl_map.h:102:11: note:   ‘std::map’
  102 |     class map
      |           ^~~
/usr/include/c++/13/map:80:13: note:   ‘std::pmr::map’
   80 |       using map
      |             ^~~

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <numeric>
#include <tuple>
#include <ctime>
#include <map>

template <class T, class U>
inline bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

template <class T, class U>
inline bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) {
    lhs = rhs;
    return true;
  }
  return false;
}

// [l, r) from l to r
struct range {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { ++i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr l, r;
  constexpr range(int l_, int r_): l(l_), r(std::max(l_, r_)) { }
  constexpr itr begin() const { return l; }
  constexpr itr end() const { return r; }
};

// [l, r) from r to l
struct revrange {
  struct itr {
    int i;
    constexpr itr(int i_): i(i_) { }
    constexpr void operator ++ () { --i; }
    constexpr int operator * () const { return i; }
    constexpr bool operator != (itr x) const { return i != x.i; }
  };
  const itr r, l;
  constexpr revrange(int l_, int r_): l(l_ - 1), r(std::max(l_, r_) - 1) { }
  constexpr itr begin() const { return r; }
  constexpr itr end() const { return l; }
};

template <class T>
class hash_string {
public:
  using mod_type = unsigned long long;
  using base_type = unsigned;
  using size_type = unsigned;
  static constexpr mod_type mod = (1ll << 61) - 1;
  static base_type base() { return T::value; }

private:
  std::string M_string;
  std::vector<mod_type> M_power, M_hash;

public:
  hash_string() { init(); }
  hash_string(const std::string &initial_) { init(initial_);}

  void init() {
    M_string = "";
    M_power.assign(1, 1);
    M_hash.assign(1, 0);
  }
  void init(const std::string &initial_) {
    init();
    add_string(initial_);
  }

  void add_string(const std::string &str) {
    size_type cur_size = M_string.size();
    size_type next_size = M_string.size() + str.size();
    M_string += str;
    M_power.resize(next_size + 1);
    M_hash.resize(next_size + 1);
    for (size_type i = cur_size; i < next_size; ++i) {
      M_power[i + 1] = (__uint128_t) M_power[i] * base() % mod;
      M_hash[i + 1] = ((__uint128_t) M_hash[i] * base() + M_string[i])% mod;
    }
  }
  
  mod_type hash(size_type l, size_type r) const {
    return (M_hash[r] + mod - ((__uint128_t) M_power[r - l] * M_hash[l]) % mod) % mod;
  }
  const std::string &get() const {
    return M_string;
  }

};

struct rolling_hash_base { static inline const unsigned value = std::clock() ^ std::time(nullptr); };
using rolling_hash = hash_string<rolling_hash_base>;

int main() {
  std::string S;
  int M;
  std::cin >> S >> M;
  std::unordered_map<unsigned long long, int> map;
  for (int i: range(0, M)) {
    std::string C;
    std::cin >> C;
    map[rolling_hash(C).hash(0, C.size())]++;
  }
  int ans = 0;
  rolling_hash hash(S);
  for (int len: range(1, std::min<int>(S.size(), 10) + 1)) {
    for (int i: range(0, S.size() - len + 1)) {
      ans += map[hash.hash(i, i + len)];
    }
  }
  std::cout << ans << '\n';
  return 0;
}
0