Submission #2125983
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; 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; } vector<mint> one_differ(int n, mint base) { mint fuga = 1; vector<mint> s; rep(i, n) { for (int i = -25; i <= 25; i++) { if (i == 0) continue; mint piyo = (mint(i) + mod) % mod; s.push_back((piyo * fuga) % mod); } (fuga *= base) %= mod; } sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end()); 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++) { bool f1 = (*lower_bound(s1.begin(), s1.end(), ((sh1 - th1) % mod + mod) % mod)) == (((sh1 - th1) % mod + mod) % mod); bool f2 = (*lower_bound(s2.begin(), s2.end(), ((sh2 - th2) % mod + mod) % mod)) == (((sh2 - th2) % mod + mod) % mod); if (f1 and f2) cnt++; if (i != s.size()) { int remove = s[i - n] - 'a'; int add = s[i] - 'a'; sh1 = (((sh1 - mint(remove) * v1) * base1 + mint(add) + mod) % mod + mod) % mod; sh2 = (((sh2 - mint(remove) * v2) * base2 + mint(add) + mod) % mod + 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 | 1994 Byte |
Status | WA |
Exec Time | 1869 ms |
Memory | 127908 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 | AC | 1772 ms | 126756 KB |
allsame28.txt | AC | 1186 ms | 107636 KB |
even.txt | AC | 3 ms | 384 KB |
hash-collide.txt | AC | 6 ms | 768 KB |
hash-collide2.txt | AC | 39 ms | 2420 KB |
hash-collide3.txt | AC | 47 ms | 2548 KB |
hash-collide4.txt | AC | 47 ms | 2548 KB |
hash-typical.txt | AC | 27 ms | 1528 KB |
hash-typical2.txt | AC | 27 ms | 1528 KB |
periodical29.txt | WA | 1772 ms | 126116 KB |
periodical30.txt | WA | 1775 ms | 126500 KB |
periodical31.txt | MLE | 1778 ms | 127652 KB |
periodical32.txt | MLE | 1773 ms | 127908 KB |
periodical33.txt | MLE | 1866 ms | 127012 KB |
periodical34.txt | MLE | 1868 ms | 127140 KB |
periodical35.txt | MLE | 1869 ms | 127524 KB |
periodical36.txt | MLE | 1866 ms | 127780 KB |
periodical37.txt | WA | 45 ms | 900 KB |
periodical38.txt | WA | 45 ms | 900 KB |
periodical39.txt | WA | 47 ms | 900 KB |
periodical40.txt | WA | 43 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 | 7 ms | 896 KB |
random15.txt | WA | 1 ms | 256 KB |
random16.txt | WA | 1 ms | 256 KB |
random17.txt | AC | 10 ms | 1404 KB |
random18.txt | WA | 47 ms | 900 KB |
random19.txt | WA | 44 ms | 900 KB |
random20.txt | WA | 502 ms | 40044 KB |
random21.txt | WA | 45 ms | 900 KB |
random22.txt | WA | 46 ms | 900 KB |
random23.txt | WA | 1169 ms | 103940 KB |
random24.txt | WA | 48 ms | 900 KB |
random25.txt | WA | 46 ms | 900 KB |
random26.txt | AC | 267 ms | 20592 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 |