Submission #3931961
Source Code Expand
#include<bits/stdc++.h> using namespace std; const int M = 1000000007; class suffix_array { // compare (rank[i], rank[i + k]) and (rank[j], rank[j + k]) static bool compare_sa(int n, const vector<int>& rank, int i, int j, int k) { if (rank[i] != rank[j]) return rank[i] < rank[j]; int ri = i + k <= n ? rank[i + k] : -1; int rj = j + k <= n ? rank[j + k] : -1; return ri < rj; } public: static vector<int> construct_sa(const string& s) { int n = s.length(); vector<int> sa(n + 1), rank(n + 1); for (int i = 0; i <= n; ++i) { sa[i] = i; rank[i] = i < n ? s[i] : -1; } for (int k = 1; k <= n; k <<= 1) { sort(sa.begin(), sa.end(), [&n, &k, &rank](const int& a, const int& b){ return compare_sa(n, rank, a, b, k); }); vector<int> tmp(n + 1); for (int i = 1; i <= n; ++i) tmp[sa[i]] = tmp[sa[i - 1]] + compare_sa(n, rank, sa[i - 1], sa[i], k); for (int i = 0; i <= n; ++i) rank[i] = tmp[i]; } return sa; } static vector<int> construct_lcp(const string& s, const vector<int>& sa) { int n = s.length(); vector<int> rank(n + 1), lcp(n + 1); for (int i = 0; i <= n; ++i) rank[sa[i]] = i; int h = 0; for (int i = 0; i < n; ++i) { if (h > 0) --h; for (int j = sa[rank[i] - 1]; j + h < n && i + h < n; ++h) if (s[j + h] != s[i + h]) break; lcp[rank[i] - 1] = h; } return lcp; } }; int main() { string s, t; cin >> s >> t; string st = s + t, rts = t + s; reverse(rts.begin(), rts.end()); vector<int> sa_st = suffix_array::construct_sa(st); vector<int> lcp_st = suffix_array::construct_lcp(st, sa_st); vector<int> sa_rts = suffix_array::construct_sa(rts); vector<int> lcp_rts = suffix_array::construct_lcp(rts, sa_rts); int st_i = -1, rts_i = -1; for (int i = 0; i < (int)sa_st.size(); ++i) { if (sa_st[i] == (int)s.length()) { st_i = i; break; } } for (int i = 0; i < (int)sa_rts.size(); ++i) { if (sa_rts[i] == (int)s.length()) { rts_i = i; break; } } vector<int> h((int)s.length() - (int)t.length() + 1); int l = M; for (int i = st_i + 1; i < (int)sa_st.size(); ++i) { l = min(l, lcp_st[i - 1]); if (l == 0) break; if (sa_st[i] < (int)h.size()) h[sa_st[i]] += l; } l = M; for (int i = st_i - 1; i >= 0; --i) { l = min(l, lcp_st[i]); if (l == 0) break; if (sa_st[i] < (int)h.size()) h[sa_st[i]] += l; } l = M; for (int i = rts_i + 1; i < (int)sa_rts.size(); ++i) { l = min(l, lcp_rts[i - 1]); if (l == 0) break; int u = (int)s.length() - sa_rts[i] - (int)t.length(); if (u >= 0 && u < (int)h.size()) h[u] += l; } l = M; for (int i = rts_i - 1; i >= 0; --i) { l = min(l, lcp_rts[i]); if (l == 0) break; int u = (int)s.length() - sa_rts[i] - (int)t.length(); if (u >= 0 && u < (int)h.size()) h[u] += l; } int ans = 0; for (int i : h) if (i == (int)t.length() - 1) ++ans; cout << ans << "\n"; return 0; }
Submission Info
Submission Time | |
---|---|
Task | H - Almost Same Substring |
User | riantkb |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 3393 Byte |
Status | AC |
Exec Time | 1266 ms |
Memory | 10632 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 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 | 256 KB |
20-teuchi1.txt | AC | 1 ms | 256 KB |
allsame27.txt | AC | 976 ms | 10632 KB |
allsame28.txt | AC | 866 ms | 9420 KB |
even.txt | AC | 2 ms | 256 KB |
hash-collide.txt | AC | 8 ms | 384 KB |
hash-collide2.txt | AC | 112 ms | 1960 KB |
hash-collide3.txt | AC | 138 ms | 2328 KB |
hash-collide4.txt | AC | 138 ms | 2376 KB |
hash-typical.txt | AC | 68 ms | 1288 KB |
hash-typical2.txt | AC | 68 ms | 1416 KB |
periodical29.txt | AC | 983 ms | 10632 KB |
periodical30.txt | AC | 1028 ms | 10632 KB |
periodical31.txt | AC | 1266 ms | 10632 KB |
periodical32.txt | AC | 968 ms | 10632 KB |
periodical33.txt | AC | 1189 ms | 10632 KB |
periodical34.txt | AC | 1191 ms | 10632 KB |
periodical35.txt | AC | 1223 ms | 10632 KB |
periodical36.txt | AC | 1175 ms | 10632 KB |
periodical37.txt | AC | 686 ms | 7004 KB |
periodical38.txt | AC | 686 ms | 7004 KB |
periodical39.txt | AC | 684 ms | 7004 KB |
periodical40.txt | AC | 687 ms | 7004 KB |
random00.txt | AC | 1 ms | 256 KB |
random01.txt | AC | 1 ms | 256 KB |
random02.txt | AC | 1 ms | 256 KB |
random03.txt | AC | 1 ms | 256 KB |
random04.txt | AC | 1 ms | 256 KB |
random05.txt | AC | 1 ms | 256 KB |
random06.txt | AC | 1 ms | 256 KB |
random07.txt | AC | 1 ms | 256 KB |
random08.txt | AC | 1 ms | 256 KB |
random09.txt | AC | 2 ms | 256 KB |
random10.txt | AC | 2 ms | 256 KB |
random11.txt | AC | 2 ms | 256 KB |
random12.txt | AC | 2 ms | 256 KB |
random13.txt | AC | 2 ms | 256 KB |
random14.txt | AC | 2 ms | 256 KB |
random15.txt | AC | 2 ms | 256 KB |
random16.txt | AC | 2 ms | 256 KB |
random17.txt | AC | 3 ms | 256 KB |
random18.txt | AC | 675 ms | 7004 KB |
random19.txt | AC | 674 ms | 7004 KB |
random20.txt | AC | 798 ms | 7884 KB |
random21.txt | AC | 675 ms | 7004 KB |
random22.txt | AC | 676 ms | 7004 KB |
random23.txt | AC | 968 ms | 9160 KB |
random24.txt | AC | 674 ms | 7004 KB |
random25.txt | AC | 675 ms | 7004 KB |
random26.txt | AC | 732 ms | 7284 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 |