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
AC × 59
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