結果

問題 No.430 文字列検索
ユーザー suisensuisen
提出日時 2021-09-08 17:00:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 5,406 bytes
コンパイル時間 1,137 ms
コンパイル使用メモリ 100,552 KB
実行使用メモリ 17,024 KB
最終ジャッジ日時 2024-11-10 00:57:26
合計ジャッジ時間 2,042 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 40 ms
17,016 KB
testcase_02 AC 13 ms
9,860 KB
testcase_03 AC 12 ms
9,864 KB
testcase_04 AC 1 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 38 ms
17,024 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 5 ms
5,248 KB
testcase_11 AC 39 ms
16,656 KB
testcase_12 AC 38 ms
16,912 KB
testcase_13 AC 40 ms
16,912 KB
testcase_14 AC 38 ms
16,656 KB
testcase_15 AC 35 ms
16,780 KB
testcase_16 AC 25 ms
16,440 KB
testcase_17 AC 23 ms
16,204 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define PROBLEM "https://yukicoder.me/problems/no/430"

#include <iostream>

#include <cassert>
#include <deque>
#include <map>
#include <string>
#include <vector>

namespace suisen {

/**
 * reference : https://w.atwiki.jp/uwicoder/pages/2842.html
 */
template <typename T, typename SequenceType>
struct SuffixAutomatonBase {
    struct Node {
        std::map<T, int> nxt;
        int link, len;
        bool cloned;
    };

    std::vector<Node> nodes;
    int last;

    SuffixAutomatonBase() {
        nodes.push_back({ {}, -1, 0, false });
        last = 0;
    }
    SuffixAutomatonBase(const SequenceType &s) : SuffixAutomatonBase() {
        for (const T &c : s) append(c);
    }

    void append(const T &c) {
        const int new_node = nodes.size();
        nodes.push_back({ {}, -1, nodes[last].len + 1, false });
        int p = last;
        for (; p != -1 and not nodes[p].nxt.count(c); p = nodes[p].link) nodes[p].nxt[c] = new_node;
        const int q = p == -1 ? 0 : nodes[p].nxt[c];
        if (p == -1 or nodes[p].len + 1 == nodes[q].len) {
            nodes[new_node].link = q;
        } else {
            const int clone_node = nodes.size();
            nodes.push_back({ nodes[q].nxt, nodes[q].link, nodes[p].len + 1, true });
            for (; p != -1 and nodes[p].nxt[c] == q; p = nodes[p].link) nodes[p].nxt[c] = clone_node;
            nodes[new_node].link = nodes[q].link = clone_node;
        }
        last = new_node;
    }
    SuffixAutomatonBase& operator+=(const T &c) {
        append(c);
        return *this;
    }

    bool accept(const SequenceType &t) const {
        int cur = 0;
        for (const auto &c : t) {
            auto it = nodes[cur].nxt.find(c);
            if (it == nodes[cur].nxt.end()) return false;
            cur = it->second;
        }
        return true;
    }

    class SubstringCounter {
        public:
            SubstringCounter(const SuffixAutomatonBase *sa, std::vector<long long> &&dp) : sa(sa), dp(std::move(dp)) {}

            long long count(const SequenceType &t) const {
                int cur = 0;
                for (const auto &c : t) {
                    auto it = sa->nodes[cur].nxt.find(c);
                    if (it == sa->nodes[cur].nxt.end()) return 0;
                    cur = it->second;
                }
                return dp[cur];
            }

        private:
            const SuffixAutomatonBase *sa;
            const std::vector<long long> dp;
    };

    SubstringCounter substring_counter() const & {
        const int n = nodes.size();
        const std::vector<int> ord = topological_order();
        std::vector<long long> dp(n, 0);
        for (int i = n - 1; i > 0; --i) {
            const int u = ord[i];
            if (not nodes[u].cloned) ++dp[u];
            dp[nodes[u].link] += dp[u];
        }
        return SubstringCounter { this, std::move(dp) };
    }
    SubstringCounter substring_counter() const && = delete;

    // returns { from, len } s.t. lcs = t[from:from+len]
    std::pair<int, int> longest_common_substring(const SequenceType &t) const {
        if (t.size() == 0) return { 0, 0 };
        const Node *v = &nodes[0];
        int l = 0, best = 0, best_pos = 0;
        for (int i = 0; i < int(t.size()); ++i){
            while (v->link != -1 and not v->nxt.count(t[i])) {
                v = &nodes[v->link];
                l = v->len;
            }
            auto it = v->nxt.find(t[i]);
            if (it != v->nxt.end()){
                v = &nodes[it->second];
                l++;
            }
            if (l > best){
                best = l;
                best_pos = i;
            }
        }
        return { best_pos - best + 1, best };
    }

    std::vector<int> topological_order() const {
        const int n = nodes.size();
        std::vector<int> in(n, 0);
        for (const auto &node : nodes) {
            for (const auto &p : node.nxt) ++in[p.second];
        }
        std::deque<int> dq;
        for (int i = 0; i < n; ++i) {
            if (in[i] == 0) dq.push_back(i);
        }
        std::vector<int> res;
        while (dq.size()) {
            int u = dq.front();
            dq.pop_front();
            res.push_back(u);
            for (const auto &p : nodes[u].nxt) {
                if (--in[p.second] == 0) dq.push_back(p.second);
            }
        }
        assert(int(res.size()) == n);
        return res;
    }
};

template <typename T>
struct SuffixAutomaton : public SuffixAutomatonBase<T, std::vector<T>> {
    using SuffixAutomatonBase<T, std::vector<T>>::SuffixAutomatonBase;
    using value_type = T;
    using sequence_type = std::vector<T>;
};

template <typename T>
SuffixAutomaton(std::vector<T>) -> SuffixAutomaton<T>;

template <>
struct SuffixAutomaton<char> : public SuffixAutomatonBase<char, std::string> {
    using SuffixAutomatonBase<char, std::string>::SuffixAutomatonBase;
    using value_type = char;
    using sequence_type = std::string;
};

SuffixAutomaton(std::string) -> SuffixAutomaton<char>;

} // namespace suisen

using suisen::SuffixAutomaton;

int main() {
    std::string s;
    std::cin >> s;
    SuffixAutomaton sa(s);
    auto counter = sa.substring_counter();
    int m;
    std::cin >> m;
    long long ans = 0;
    while (m --> 0) {
        std::string c;
        std::cin >> c;
        ans += counter.count(c);
    }
    std::cout << ans << '\n';
    return 0;
}
0