test/aoj/aoj_2863.test.cpp

• View this file on GitHub
• Last update: 2024-05-23 18:52:03+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2863

Depends on

• modint/base.hpp
• modint/modint.hpp
• string/aho_corasick.hpp
• string/trie.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2863"

#include <iostream>

#include <string>

#include <vector>


#include "../../modint/modint.hpp"

#include "../../string/aho_corasick.hpp"


using mint = ebi::modint1000000007;

int main() {
    int n;
    std::cin >> n;
    ebi::aho_corasick<26, 'a'> aho;
    std::vector<std::string> s(n);
    for (int i = 0; i < n; i++) {
        std::cin >> s[i];
        aho.add(s[i]);
    }
    aho.build();
    std::string t;
    std::cin >> t;
    int m = t.size();
    std::vector<mint> dp(m + 1, 0);
    dp[0] = 1;
    aho.query(t, [&](int i, int idx) -> void {
        dp[idx + 1] += dp[idx + 1 - int(s[i].size())];
    });
    std::cout << dp[m].val() << '\n';
}

#line 1 "test/aoj/aoj_2863.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2863"

#include <iostream>

#include <string>

#include <vector>


#line 2 "modint/modint.hpp"

#include <cassert>

#line 5 "modint/modint.hpp"

#line 2 "modint/base.hpp"

#include <concepts>
#line 5 "modint/base.hpp"
#include <utility>

namespace ebi {

template <class T>
concept Modint = requires(T a, T b) {
    a + b;
    a - b;
    a * b;
    a / b;
    a.inv();
    a.val();
    a.pow(std::declval<long long>());
    T::mod();
};

template <Modint mint> std::istream &operator>>(std::istream &os, mint &a) {
    long long x;
    os >> x;
    a = x;
    return os;
}

template <Modint mint>
std::ostream &operator<<(std::ostream &os, const mint &a) {
    return os << a.val();
}

}  // namespace ebi
#line 7 "modint/modint.hpp"

namespace ebi {

template <int m> struct static_modint {
  private:
    using modint = static_modint;

  public:
    static constexpr int mod() {
        return m;
    }

    static constexpr modint raw(int v) {
        modint x;
        x._v = v;
        return x;
    }

    constexpr static_modint() : _v(0) {}

    template <std::signed_integral T> constexpr static_modint(T v) {
        long long x = (long long)(v % (long long)(umod()));
        if (x < 0) x += umod();
        _v = (unsigned int)(x);
    }

    template <std::unsigned_integral T> constexpr static_modint(T v) {
        _v = (unsigned int)(v % umod());
    }

    constexpr unsigned int val() const {
        return _v;
    }

    constexpr unsigned int value() const {
        return val();
    }

    constexpr modint &operator++() {
        _v++;
        if (_v == umod()) _v = 0;
        return *this;
    }
    constexpr modint &operator--() {
        if (_v == 0) _v = umod();
        _v--;
        return *this;
    }

    constexpr modint operator++(int) {
        modint res = *this;
        ++*this;
        return res;
    }
    constexpr modint operator--(int) {
        modint res = *this;
        --*this;
        return res;
    }

    constexpr modint &operator+=(const modint &rhs) {
        _v += rhs._v;
        if (_v >= umod()) _v -= umod();
        return *this;
    }
    constexpr modint &operator-=(const modint &rhs) {
        _v -= rhs._v;
        if (_v >= umod()) _v += umod();
        return *this;
    }
    constexpr modint &operator*=(const modint &rhs) {
        unsigned long long x = _v;
        x *= rhs._v;
        _v = (unsigned int)(x % (unsigned long long)umod());
        return *this;
    }
    constexpr modint &operator/=(const modint &rhs) {
        return *this = *this * rhs.inv();
    }

    constexpr modint operator+() const {
        return *this;
    }
    constexpr modint operator-() const {
        return modint() - *this;
    }

    constexpr modint pow(long long n) const {
        assert(0 <= n);
        modint x = *this, res = 1;
        while (n) {
            if (n & 1) res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
    constexpr modint inv() const {
        assert(_v);
        return pow(umod() - 2);
    }

    friend modint operator+(const modint &lhs, const modint &rhs) {
        return modint(lhs) += rhs;
    }
    friend modint operator-(const modint &lhs, const modint &rhs) {
        return modint(lhs) -= rhs;
    }
    friend modint operator*(const modint &lhs, const modint &rhs) {
        return modint(lhs) *= rhs;
    }

    friend modint operator/(const modint &lhs, const modint &rhs) {
        return modint(lhs) /= rhs;
    }
    friend bool operator==(const modint &lhs, const modint &rhs) {
        return lhs.val() == rhs.val();
    }
    friend bool operator!=(const modint &lhs, const modint &rhs) {
        return !(lhs == rhs);
    }

  private:
    unsigned int _v = 0;

    static constexpr unsigned int umod() {
        return m;
    }
};

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;

}  // namespace ebi
#line 2 "string/aho_corasick.hpp"

#include <string.h>


#include <algorithm>

#line 7 "string/aho_corasick.hpp"
#include <map>

#include <queue>

#line 10 "string/aho_corasick.hpp"

#line 2 "string/trie.hpp"

#include <array>

#line 7 "string/trie.hpp"

namespace ebi {

template <int char_size, int margin> struct trie {
  private:
    struct trie_node {
        int common;
        std::array<int, char_size> nxt;
        std::vector<int> accept;
        trie_node() : common(0) {
            nxt.fill(-1);
        }
    };

  public:
    trie() {
        nodes.emplace_back(trie_node());
    }

    void add(const std::string &str) {
        int idx = 0;
        for (const auto &c : str) {
            int val = c - margin;
            assert(0 <= val && val < char_size);
            if (nodes[idx].nxt[val] < 0) {
                nodes[idx].nxt[val] = int(nodes.size());
                nodes.emplace_back(trie_node());
            }
            idx = nodes[idx].nxt[val];
            nodes[idx].common++;
        }
        nodes[idx].accept.emplace_back(nodes[0].common++);
    }

    template <class F>
    void query(const std::string &str, int start, F func) const {
        int idx = 0;
        for (int i = start; i < int(str.size()); ++i) {
            int val = str[i] - margin;
            assert(0 <= val && val < char_size);
            int nxt = nodes[idx].nxt[val];
            if (nxt < 0) {
                return;
            }
            idx = nxt;
            for (const auto id : nodes[idx].accept) {
                func(id);
            }
        }
        return;
    }

    bool search(const std::string &str, int start, bool prefix = false) const {
        int idx = 0;
        for (int i = start; i < int(str.size()); ++i) {
            int val = str[i] - margin;
            assert(0 <= val && val < char_size);
            int nxt = nodes[idx].nxt[val];
            if (nxt < 0) {
                return -1;
            }
            idx = nxt;
        }
        return prefix ? true : (nodes[idx].accept.size() > 0);
    }

    int size() const {
        return int(nodes.size());
    }

  protected:
    std::vector<trie_node> nodes;
};

}  // namespace ebi
#line 12 "string/aho_corasick.hpp"

namespace ebi {

template <int char_size, int margin>
struct aho_corasick : trie<char_size + 1, margin> {
  private:
    void move_nxt(int &now, int val) {
        assert(0 <= val && val < char_size);
        while (this->nodes[now].nxt[val] == -1)
            now = this->nodes[now].nxt[FAIL];
        now = this->nodes[now].nxt[val];
        return;
    }
    using trie<char_size + 1, margin>::trie;
    using trie<char_size + 1, margin>::nodes;

  public:
    void build() {
        correct.resize(this->size());
        for (int i = 0; i < this->size(); ++i) {
            correct[i] = int(this->nodes[i].accept.size());
        }
        std::queue<int> que;
        for (int i = 0; i <= char_size; ++i) {
            if (this->nodes[0].nxt[i] != -1) {
                this->nodes[this->nodes[0].nxt[i]].nxt[FAIL] = 0;
                que.push(this->nodes[0].nxt[i]);
            } else {
                this->nodes[0].nxt[i] = 0;
            }
        }
        while (!que.empty()) {
            int idx = que.front();
            que.pop();
            auto &now = this->nodes[idx];
            correct[idx] += correct[now.nxt[FAIL]];
            for (int i = 0; i < char_size; ++i) {
                if (now.nxt[i] == -1) continue;
                int fail = now.nxt[FAIL];
                while (this->nodes[fail].nxt[i] == -1)
                    fail = this->nodes[fail].nxt[FAIL];
                this->nodes[now.nxt[i]].nxt[FAIL] = this->nodes[fail].nxt[i];
                std::vector<int> &u = this->nodes[now.nxt[i]].accept;
                std::vector<int> &v =
                    this->nodes[this->nodes[fail].nxt[i]].accept;
                std::vector<int> accept;
                std::set_union(u.begin(), u.end(), v.begin(), v.end(),
                               std::back_inserter(accept));
                u = accept;
                que.push(now.nxt[i]);
            }
        }
    }

    std::map<int, int> match(const std::string &str, int now = 0) {
        std::map<int, int> map;
        for (const auto &c : str) {
            move_nxt(now, c - margin);
            for (const auto &a : this->nodes[now].accept) {
                map[a]++;
            }
        }
        return map;
    }

    template <class F> void query(const std::string &str, F func, int now = 0) {
        for (int i = 0; i < int(str.size()); ++i) {
            move_nxt(now, str[i] - margin);
            for (const auto &a : this->nodes[now].accept) {
                func(a, i);
            }
        }
        return;
    }

    std::pair<int, int> move(const char &c, int now) {
        int sum = 0;
        move_nxt(now, c - margin);
        sum += correct[now];
        return {sum, now};
    }

  private:
    const int FAIL = char_size;
    std::vector<int> correct;
};

}  // namespace ebi

#line 9 "test/aoj/aoj_2863.test.cpp"

using mint = ebi::modint1000000007;

int main() {
    int n;
    std::cin >> n;
    ebi::aho_corasick<26, 'a'> aho;
    std::vector<std::string> s(n);
    for (int i = 0; i < n; i++) {
        std::cin >> s[i];
        aho.add(s[i]);
    }
    aho.build();
    std::string t;
    std::cin >> t;
    int m = t.size();
    std::vector<mint> dp(m + 1, 0);
    dp[0] = 1;
    aho.query(t, [&](int i, int idx) -> void {
        dp[idx + 1] += dp[idx + 1 - int(s[i].size())];
    });
    std::cout << dp[m].val() << '\n';
}

Back to top page