Submission #2125933
Source Code Expand
#include <bits/stdc++.h> #define rep(i, n) for (lli i = 0; i < (n); i++) #define rrep(i, n) for (lli i = (n)-1; i >= 0; i--) using namespace std; using lli = long long int; // template <signed M, unsigned T> // struct mod_int { // constexpr static signed MODULO = M; // constexpr static unsigned TABLE_SIZE = T; // // signed x; // // mod_int() : x(0) {} // // mod_int(long long y) : x(static_cast<signed>(y >= 0 ? y % MODULO : MODULO - (-y) % MODULO)) {} // // mod_int(int y) : x(y >= 0 ? y % MODULO : MODULO - (-y) % MODULO) {} // // mod_int& operator+=(const mod_int& rhs) // { // if ((x += rhs.x) >= MODULO) // x -= MODULO; // return *this; // } // // mod_int& operator-=(const mod_int& rhs) // { // if ((x += MODULO - rhs.x) >= MODULO) // x -= MODULO; // return *this; // } // // mod_int& operator*=(const mod_int& rhs) // { // x = static_cast<signed>(1LL * x * rhs.x % MODULO); // return *this; // } // // mod_int& operator/=(const mod_int& rhs) // { // x = static_cast<signed>((1LL * x * rhs.inv().x) % MODULO); // return *this; // } // // mod_int operator-() const { return mod_int(-x); } // // mod_int operator+(const mod_int& rhs) const { return mod_int(*this) += rhs; } // // mod_int operator-(const mod_int& rhs) const { return mod_int(*this) -= rhs; } // // mod_int operator*(const mod_int& rhs) const { return mod_int(*this) *= rhs; } // // mod_int operator/(const mod_int& rhs) const { return mod_int(*this) /= rhs; } // // bool operator<(const mod_int& rhs) const { return x < rhs.x; } // // mod_int inv() const // { // assert(x != 0); // if (x <= static_cast<signed>(TABLE_SIZE)) { // if (_inv[1].x == 0) // prepare(); // return _inv[x]; // } else { // signed a = x, b = MODULO, u = 1, v = 0, t; // while (b) { // t = a / b; // a -= t * b; // std::swap(a, b); // u -= t * v; // std::swap(u, v); // } // return mod_int(u); // } // } // // mod_int pow(long long t) const // { // assert(!(x == 0 && t == 0)); // mod_int e = *this, res = mod_int(1); // for (; t; e *= e, t >>= 1) // if (t & 1) // res *= e; // return res; // } // // mod_int fact() // { // if (_fact[0].x == 0) // prepare(); // return _fact[x]; // } // // mod_int inv_fact() // { // if (_fact[0].x == 0) // prepare(); // return _inv_fact[x]; // } // // mod_int choose(mod_int y) // { // assert(y.x <= x); // return this->fact() * y.inv_fact() * mod_int(x - y.x).inv_fact(); // } // // static mod_int _inv[TABLE_SIZE + 1]; // // static mod_int _fact[TABLE_SIZE + 1]; // // static mod_int _inv_fact[TABLE_SIZE + 1]; // // static void prepare() // { // _inv[1] = 1; // for (int i = 2; i <= (int)TABLE_SIZE; ++i) { // _inv[i] = 1LL * _inv[MODULO % i].x * (MODULO - MODULO / i) % MODULO; // } // _fact[0] = 1; // for (unsigned i = 1; i <= TABLE_SIZE; ++i) { // _fact[i] = _fact[i - 1] * int(i); // } // _inv_fact[TABLE_SIZE] = _fact[TABLE_SIZE].inv(); // for (int i = (int)TABLE_SIZE - 1; i >= 0; --i) { // _inv_fact[i] = _inv_fact[i + 1] * (i + 1); // } // } // }; // // template <int M, unsigned F> // std::ostream& operator<<(std::ostream& os, const mod_int<M, F>& rhs) // { // return os << rhs.x; // } // // template <int M, unsigned F> // std::istream& operator>>(std::istream& is, mod_int<M, F>& rhs) // { // long long s; // is >> s; // rhs = mod_int<M, F>(s); // return is; // } // // template <int M, unsigned F> // mod_int<M, F> mod_int<M, F>::_inv[TABLE_SIZE + 1]; // // template <int M, unsigned F> // mod_int<M, F> mod_int<M, F>::_fact[TABLE_SIZE + 1]; // // template <int M, unsigned F> // mod_int<M, F> mod_int<M, F>::_inv_fact[TABLE_SIZE + 1]; // // template <int M, unsigned F> // bool operator==(const mod_int<M, F>& lhs, const mod_int<M, F>& rhs) // { // return lhs.x == rhs.x; // } // // template <int M, unsigned F> // bool operator!=(const mod_int<M, F>& lhs, const mod_int<M, F>& rhs) // { // return !(lhs == rhs); // } // // const int MF = 1; //割り算しないなら // const int MOD = 1000000007; // // using mint = mod_int<MOD, MF>; // // mint binom(int n, int r) // { // return (r < 0 || r > n || n < 0) ? 0 : mint(n).choose(r); // } // // mint fact(int n) // { // return mint(n).fact(); // } // // mint inv_fact(int n) // { // return mint(n).inv_fact(); // } using mint = lli; lli mod = 1e9 + 7; mint get_hash(string t, mint base) { int n = t.size(); mint val = 0; rep(i, n) val = (val * base + mint(t[i] - 'a') + mod) % mod; return val; } set<mint> one_differ(int n, mint base) { mint fuga = 1; set<mint> s; rep(i, n) { for (int i = 1; i <= 25; i++) { mint piyo = mint(i); s.insert((piyo * fuga) % mod); } (fuga *= base) %= mod; } return s; } int main() { string s, t; mint base1 = 97, base2 = 103; cin >> s >> t; int n = t.size(); string tmp = s.substr(0, n); auto th1 = get_hash(t, base1); auto th2 = get_hash(t, base2); auto sh1 = get_hash(tmp, base1); auto sh2 = get_hash(tmp, base2); auto s1 = one_differ(n, base1); auto s2 = one_differ(n, base2); mint v1 = 1, v2 = 1; rep(i, n - 1)(v1 *= base1) %= mod, (v2 *= base2) %= mod; int cnt = 0; for (int i = n; i < s.size() + 1; i++) { if ((s1.find(sh1 - th1) != s1.end() and s2.find(sh2 - th2) != s2.end()) or ((s1.find(th1 - sh1) != s1.end() and s2.find(th2 - sh2) != s2.end()))) cnt++; int remove = s[i - n] - 'a'; int add = s[i] - 'a'; if (i != s.size()) { sh1 = ((sh1 - mint(remove) * v1) * base1 + mint(add) + mod) % mod; sh2 = ((sh2 - mint(remove) * v2) * base2 + mint(add) + mod) % mod; } } cout << cnt << endl; }
Submission Info
Submission Time | |
---|---|
Task | H - Almost Same Substring |
User | uenoku |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 6591 Byte |
Status | WA |
Exec Time | 4223 ms |
Memory | 268420 KB |
Judge Result
Set Name | All | ||||||
---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||||
Status |
|
Set Name | Test Cases |
---|---|
All | 00-sample1.txt, 100000007.txt, 20-teuchi1.txt, allsame27.txt, allsame28.txt, even.txt, hash-collide.txt, hash-collide2.txt, hash-collide3.txt, hash-collide4.txt, hash-typical.txt, hash-typical2.txt, periodical29.txt, periodical30.txt, periodical31.txt, periodical32.txt, periodical33.txt, periodical34.txt, periodical35.txt, periodical36.txt, periodical37.txt, periodical38.txt, periodical39.txt, periodical40.txt, random00.txt, random01.txt, random02.txt, random03.txt, random04.txt, random05.txt, random06.txt, random07.txt, random08.txt, random09.txt, random10.txt, random11.txt, random12.txt, random13.txt, random14.txt, random15.txt, random16.txt, random17.txt, random18.txt, random19.txt, random20.txt, random21.txt, random22.txt, random23.txt, random24.txt, random25.txt, random26.txt, teuti01.txt, teuti02.txt, teuti03.txt, teuti04.txt, teuti05.txt, teuti06.txt, teuti07.txt, teuti08.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00-sample1.txt | AC | 1 ms | 256 KB |
100000007.txt | AC | 2 ms | 384 KB |
20-teuchi1.txt | AC | 1 ms | 256 KB |
allsame27.txt | TLE | 4221 ms | 244484 KB |
allsame28.txt | TLE | 4218 ms | 237188 KB |
even.txt | AC | 3 ms | 640 KB |
hash-collide.txt | AC | 6 ms | 1152 KB |
hash-collide2.txt | AC | 34 ms | 3456 KB |
hash-collide3.txt | AC | 41 ms | 3968 KB |
hash-collide4.txt | AC | 40 ms | 3968 KB |
hash-typical.txt | AC | 25 ms | 2944 KB |
hash-typical2.txt | AC | 26 ms | 2944 KB |
periodical29.txt | TLE | 4219 ms | 255364 KB |
periodical30.txt | TLE | 4223 ms | 257924 KB |
periodical31.txt | TLE | 4219 ms | 248324 KB |
periodical32.txt | TLE | 4218 ms | 255468 KB |
periodical33.txt | TLE | 4220 ms | 268420 KB |
periodical34.txt | TLE | 4220 ms | 253700 KB |
periodical35.txt | TLE | 4219 ms | 254340 KB |
periodical36.txt | TLE | 4220 ms | 256516 KB |
periodical37.txt | WA | 23 ms | 900 KB |
periodical38.txt | WA | 25 ms | 900 KB |
periodical39.txt | WA | 23 ms | 900 KB |
periodical40.txt | WA | 23 ms | 900 KB |
random00.txt | WA | 1 ms | 256 KB |
random01.txt | AC | 1 ms | 256 KB |
random02.txt | AC | 1 ms | 256 KB |
random03.txt | WA | 1 ms | 256 KB |
random04.txt | WA | 1 ms | 256 KB |
random05.txt | AC | 1 ms | 256 KB |
random06.txt | WA | 1 ms | 256 KB |
random07.txt | AC | 1 ms | 256 KB |
random08.txt | AC | 1 ms | 256 KB |
random09.txt | WA | 1 ms | 256 KB |
random10.txt | WA | 1 ms | 256 KB |
random11.txt | AC | 1 ms | 256 KB |
random12.txt | WA | 1 ms | 256 KB |
random13.txt | WA | 1 ms | 256 KB |
random14.txt | AC | 8 ms | 1792 KB |
random15.txt | WA | 1 ms | 256 KB |
random16.txt | WA | 1 ms | 256 KB |
random17.txt | AC | 12 ms | 2432 KB |
random18.txt | WA | 24 ms | 900 KB |
random19.txt | WA | 26 ms | 900 KB |
random20.txt | AC | 1173 ms | 80388 KB |
random21.txt | WA | 25 ms | 900 KB |
random22.txt | WA | 25 ms | 900 KB |
random23.txt | TLE | 4216 ms | 208900 KB |
random24.txt | WA | 24 ms | 900 KB |
random25.txt | WA | 25 ms | 900 KB |
random26.txt | AC | 364 ms | 30596 KB |
teuti01.txt | AC | 1 ms | 256 KB |
teuti02.txt | AC | 1 ms | 256 KB |
teuti03.txt | AC | 1 ms | 256 KB |
teuti04.txt | AC | 1 ms | 256 KB |
teuti05.txt | AC | 1 ms | 256 KB |
teuti06.txt | AC | 1 ms | 256 KB |
teuti07.txt | AC | 1 ms | 256 KB |
teuti08.txt | AC | 1 ms | 256 KB |