#941235 (C++14) No.430 文字列検索

提出ソース

結果

問題	No.430 文字列検索
ユーザー	zoidzium
提出日時	2023-12-30 13:43:00
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	635 ms / 2,000 ms
コード長	8,612 bytes
コンパイル時間	2,316 ms
コンパイル使用メモリ	196,464 KB
実行使用メモリ	157,180 KB
最終ジャッジ日時	2023-12-30 13:43:06
合計ジャッジ時間	5,568 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	613 ms 157,180 KB
testcase_02	AC	67 ms 6,676 KB
testcase_03	AC	69 ms 6,676 KB
testcase_04	AC	2 ms 6,676 KB
testcase_05	AC	2 ms 6,676 KB
testcase_06	AC	2 ms 6,676 KB
testcase_07	AC	2 ms 6,676 KB
testcase_08	AC	635 ms 156,892 KB
testcase_09	AC	2 ms 6,676 KB
testcase_10	AC	40 ms 18,560 KB
testcase_11	AC	188 ms 29,172 KB
testcase_12	AC	178 ms 29,172 KB
testcase_13	AC	187 ms 29,300 KB
testcase_14	AC	135 ms 18,396 KB
testcase_15	AC	112 ms 12,544 KB
testcase_16	AC	72 ms 6,676 KB
testcase_17	AC	78 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using xy = pair<ll, ll>;
using uxy = pair<ull, ull>;
using zzz = tuple<ll, ll, ll>;

using vl = vector<ll>;
using vul = vector<ull>;
using vxy = vector<xy>;
using vuxy = vector<uxy>;
using vzzz = vector<zzz>;
using vs = vector<string>;

using vvl = vector<vl>;
using vvxy = vector<vxy>;
using vvzzz = vector<vzzz>;

using vvvl = vector<vvl>;
using vvvxy = vector<vvxy>;
using vvvzzz = vector<vvzzz>;

#define rep(i, n) for (long long i = 0; i < (n); i++)
#define cnt(i, n, m) for (long long i = (n); i <= (m); i++)
#define echo(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++)
#define recho(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++)
#define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl;
#define nth(a, b) (((a) >> (b)) & 1)

class hash1 {
  static unordered_map<ull, ull> Hs;
  static unordered_map<ull, unordered_map<ull, unordered_map<ull, ull>>> Hs3;
  static ull Cnt;
  static ull ME31;
  static ull ME30;
  static ull M1;
  static ull M2;
  static ull M3;
  static ull D;
  static ull Inv1;
  static ull Inv2;
  static ull Inv3;

 private:
  ull E1 = 0;
  ull E2 = 0;
  ull E3 = 0;
  ull Len;
  ull B1;
  ull B2;
  ull B3;

 public:
  hash1() : E1(0ULL), E2(0ULL), E3(0ULL), Len(0), B1(1ULL), B2(1ULL), B3(1ULL) {
    if (Cnt == 0) {
      ME31 = ((1ULL << 31) - 1ULL);
      ME30 = ((1ULL << 30) - 1ULL);
      M1 = ((1ULL << 61) - 1ULL);
      M2 = (2147483647ULL);
      M3 = (1000000007ULL);
      D = (67);
      Inv1 = (hash1::inv61(D));
      Inv2 = (hash1::inv(D, M2));
      Inv3 = (hash1::inv(D, M3));
    }
    Cnt++;
  };

  hash1(const string& S)
      : E1(0ULL), E2(0ULL), E3(0ULL), Len(0), B1(1ULL), B2(1ULL), B3(1ULL) {
    if (Cnt == 0) {
      ME31 = ((1ULL << 31) - 1ULL);
      ME30 = ((1ULL << 30) - 1ULL);
      M1 = ((1ULL << 61) - 1ULL);
      M2 = (2147483647ULL);
      M3 = (1000000007ULL);
      D = (67);
      Inv1 = (hash1::inv61(D));
      Inv2 = (hash1::inv(D, M2));
      Inv3 = (hash1::inv(D, M3));
    }
    Cnt++;
    this->setStr(S);
  };

 private:
  static ull inv(const ull& D, const ull M) {
    ull X = 1ULL;
    ull A = D;
    ull N = M - 2ULL;
    while (N > 0) {
      if (N & 1) X = (X * A) % M;
      A = (A * A) % M;
      N /= 2;
    }
    return X;
  };
  static ull inv61(const ull& D) {
    ull X = 1ULL;
    ull A = D;
    ull N = M1 - 2ULL;
    while (N > 0) {
      if (N & 1) X = hash1::mul61(X, A);
      A = hash1::mul61(A, A);
      N /= 2;
    }
    return X;
  };
  static ull mul61(const ull& A, const ull& B) {
    ull Au = A >> 31, Av = A & ME31;
    ull Bu = B >> 31, Bv = B & ME31;
    ull AB = Au * Bv + Av * Bu;
    ull ABu = AB >> 30, ABv = AB & ME30;
    ull X = Au * Bu * 2 + ABu + (ABv << 31) + Av * Bv;
    return mod61(X);
  };
  static ull mod61(const ull& X) {
    ull Xu = X >> 61;
    ull Xv = X & M1;
    ull Y = Xu + Xv;
    if (Y >= M1) Y -= M1;
    return Y;
  };

 public:
  static ull CtoUL(const char& C) {
    if (C == ' ') return 0ULL;
    ull X = C + 1 - '0';
    if (C >= 'A') X -= 7;
    if (C >= 'a') X -= 6;
    return X;
  };
  static char ULtoC(const ull& X) {
    if (X == 0ULL) return ' ';
    char C = (char)(X - 1 + '0');
    if (C > '9') C += 7;
    if (C >= 'Z') C += 6;
    return C;
  };

 public:
  void push_back(const char& C) {
    Len++;
    ull E = hash1::CtoUL(C);
    E1 = mod61(E1 + hash1::mul61(E, B1));
    E2 = (E2 + ((E * B2) % M2));
    E3 = (E3 + ((E * B3) % M3));
    if (E2 >= M2) E2 -= M2;
    if (E3 >= M3) E3 -= M3;

    B1 = hash1::mul61(B1, D);
    B2 = (B2 * D) % M2;
    B3 = (B3 * D) % M3;
  };
  void push_front(const char& C) {
    Len++;
    ull E = hash1::CtoUL(C);
    E1 = mod61(hash1::mul61(E1, D) + E);
    E2 = (((E2 * D) % M2) + E);
    E3 = (((E3 * D) % M3) + E);
    if (E2 >= M2) E2 -= M2;
    if (E3 >= M3) E3 -= M3;

    B1 = hash1::mul61(B1, D);
    B2 = (B2 * D) % M2;
    B3 = (B3 * D) % M3;
    if (B2 >= M2) B2 -= M2;
    if (B3 >= M3) B3 -= M3;
  };
  void setStr(const string& S) {
    for (auto ite = S.begin(), end = S.end(); ite != end; ite++)
      push_back((char)*ite);
  };
  void pop_back(const char& C) {
    if (Len == 0) return;
    Len--;
    ull E = hash1::CtoUL(C);
    B1 = hash1::mul61(B1, Inv1);
    B2 = (B2 * Inv2) % M2;
    B3 = (B3 * Inv3) % M3;

    E1 = mod61(M1 + E1 - hash1::mul61(E, B1));
    E2 = (M2 + E2 - ((E * B2) % M2));
    E3 = (M3 + E3 - ((E * B3) % M3));
    if (E2 >= M2) E2 -= M2;
    if (E3 >= M3) E3 -= M3;
  }
  void pop_front(const char& C) {
    if (Len == 0) return;
    Len--;
    ull E = hash1::CtoUL(C);

    E1 = (M1 + E1 - E);
    if (E1 >= M1) E1 -= M1;
    E1 = hash1::mul61(E1, Inv1);
    E2 = (((M2 + E2 - E) % M2) * Inv2) % M2;
    E3 = (((M3 + E3 - E) % M3) * Inv3) % M3;

    B1 = hash1::mul61(B1, Inv1);
    B2 = (B2 * Inv2) % M2;
    B3 = (B3 * Inv3) % M3;
  };

  void addNum(const ull& X) {
    E1 = mod61(E1 + X);
    E2 = (E2 + X);
    E3 = (E3 + X);
    if (E2 >= M2) E2 -= M2;
    if (E3 >= M3) E3 -= M3;
  };
  void subNum(const ull& X) {
    E1 = mod61(M1 + E1 - X);
    E2 = (M2 + E2 - X);
    E3 = (M3 + E3 - X);
    if (E2 >= M2) E2 -= M2;
    if (E3 >= M3) E3 -= M3;
  };
  vul getNum() {
    vul ANS(3);
    ANS[0] = this->E1;
    ANS[1] = this->E2;
    ANS[2] = this->E3;
    return ANS;
  }
  bool same(hash1& Comp) {
    vul Vec1 = this->getNum();
    vul Vec2 = Comp.getNum();
    return (Vec1 == Vec2);
  }
  bool same1(hash1& Comp) {
    vul Vec1 = this->getNum();
    vul Vec2 = Comp.getNum();
    return (Vec1[0] == Vec2[0]);
  }

  bool Hmake(const ull& X) { return hash1::Href(X, false); };
  bool Hset(const ull& X) { return hash1::Href(X, true); };
  bool Href(const ull& X, const bool& B) {
    auto HH1 = hash1::Hs3.find(this->E1);
    if (HH1 == hash1::Hs3.end()) {
      hash1::Hs3.emplace(this->E1,
                         unordered_map<ull, unordered_map<ull, ull>>());
      HH1 = hash1::Hs3.find(this->E1);
    }

    auto HH2 = HH1->second.find(this->E2);
    if (HH2 == HH1->second.end()) {
      HH1->second.emplace(this->E2, unordered_map<ull, ull>());
      HH2 = HH1->second.find(this->E2);
    }

    auto HH3 = HH2->second.find(this->E3);
    if (HH3 == HH2->second.end()) {
      HH2->second.emplace(this->E3, X);
      return true;
    }
    if (!B) return false;
    HH3->second = X;
    return true;
  };
  pair<bool, ull> Hfind() {
    auto HH1 = hash1::Hs3.find(this->E1);
    if (HH1 == hash1::Hs3.end()) return make_pair(false, 0ULL);
    auto HH2 = HH1->second.find(this->E2);
    if (HH2 == HH1->second.end()) return make_pair(false, 0ULL);
    auto HH3 = HH2->second.find(this->E3);
    if (HH3 == HH2->second.end()) return make_pair(false, 0ULL);
    return make_pair(true, HH3->second);
  }

  bool Hmake1(const ull& X) { return hash1::Href1(X, false); };
  bool Hset1(const ull& X) { return hash1::Href1(X, true); };
  bool Href1(const ull& X, const bool& B) {
    auto HH1 = hash1::Hs.find(this->E1);
    if (HH1 == hash1::Hs.end()) {
      hash1::Hs.emplace(this->E1, X);
      return true;
    }
    if (!B) return false;
    HH1->second = X;
    return true;
  };
  pair<bool, ull> Hfind1() {
    auto HH1 = hash1::Hs.find(this->E1);
    if (HH1 == hash1::Hs.end()) return make_pair(false, 0ULL);
    return make_pair(true, HH1->second);
  }

  void show() {
    printf("--- SHOW ---\n");
    printf("Len=%lld\n", this->Len);
    ll TMP = E1;
    string S;
    rep(i, Len) {
      if ((TMP % D) != 0) {
        S.push_back(hash1::ULtoC((TMP % D)));

      } else {
        S.push_back(' ');
      }
      TMP = mod61(M1 + TMP - (TMP % D));
      TMP = hash1::mul61(TMP, this->Inv1);
    }
    printf("[%s]\n", S.c_str());
    printf(" B1=%019lld\n", E1);
    printf(" B2=%019lld\n", E2);
    printf(" B3=%019lld\n", E3);
  };
};
unordered_map<ull, ull> hash1::Hs;
unordered_map<ull, unordered_map<ull, unordered_map<ull, ull>>> hash1::Hs3;
ull hash1::Cnt = 0;
ull hash1::ME31;
ull hash1::ME30;
ull hash1::M1;
ull hash1::M2;
ull hash1::M3;
ull hash1::D;
ull hash1::Inv1;
ull hash1::Inv2;
ull hash1::Inv3;

int main() {
  string SS;
  cin >> SS;
  ll N = SS.size();
  ll M;
  cin >> M;
  vs S(M);
  rep(i, M) cin >> S[i];
  ll L = SS.size();
  rep(i, L) {
    hash1 E;
    cnt(j, i, min<ll>(N - 1, i + 9)) {
      E.push_back(SS[j]);
      // E.show();
      E.Hset(E.Hfind().second + 1);
    }
  }

  ll ANS = 0;
  rep(i, M) {
    hash1 E(S[i]);

    // cout << "[" << i << "]=" << E.Hfind().second << "  ANS=" << ANS << endl;
    ANS += (E.Hfind().second);
  }
  cout << ANS << endl;

  return 0;
}

yukicoder

結果

テストケース

ソースコード