test/aoj2257.test.cpp

View this file on GitHub
Last update: 2021-06-21 15:24:20+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2257

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2257"
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#include "../util/modint.cpp"
#include "../datastructure/ahocorasick.cpp"

mint dp[32][501][601][2];
int to[601][501];
int to2[601][501];
int dp0[601];
void solve(int n, int m, int K){
    vector<string> words;
    vector<vector<int>> G;
    fill(dp0, dp0+601, 0);
    vector<string> kigo(K);
    int sz = 0;
    {
        int cur = 0;
        map<string, int> exist;
        for (int i = 0; i < n; ++i) {
            string s, t;
            cin >> s >> t;
            if(!exist.count(s)) {
                exist[s] = cur++;
                words.emplace_back(s);
                G.emplace_back();
            }
            if(!exist.count(t)){
                exist[t] = cur++;
                words.emplace_back(t);
                G.emplace_back();
            }
            G[exist[s]].emplace_back(exist[t]);
        }
        n = words.size();
        AhoCorasick<26, 'a'> aho;
        for (int i = 0; i < K; ++i) {
            cin >> kigo[i];
            dp0[aho.add(kigo[i])]++;
        }
        aho.build();
        for (auto &&i : aho.ord) if(i) dp0[i] += dp0[aho.v[i].fail];
        sz = aho.v.size();
        for (int i = 0; i < sz; ++i) {
            for (int j = 0; j < n; ++j) {
                to[i][j] = i;
                to2[i][j] = 0;
                for (auto &&c : words[j]) {
                    to[i][j] = aho.next(to[i][j], c);
                    to2[i][j] += dp0[to[i][j]];
                }
            }
        }
    }
    for (int i = 0; i < 32; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < sz; ++k) {
                for (int l = 0; l < 2; ++l) {
                    dp[i][j][k][l] = 0;
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if(to2[0][i] < 2) dp[words[i].size()&31][i][to[0][i]][to2[0][i]] += mint(1);
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < sz; ++k) {
                for (int l = 0; l < 2; ++l) {
                    dp[(i+22)&31][j][k][l] = 0;
                }
            }
        }
        for (int o = 0; o < n; ++o) {
            for (auto &&j : G[o]) {
                if(i+words[j].size() > m) continue;
                int now = i&31, next = (now+words[j].size())&31;
                for (int k = 0; k < sz; ++k) {
                    for (int l = 0; l < 2; ++l) {
                        if(l + to2[k][j] >= 2) continue;
                        dp[next][j][to[k][j]][l+to2[k][j]] += dp[now][o][k][l];
                    }
                }
            }
        }
    }
    mint ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < sz; ++j) {
            ans += dp[m&31][i][j][1];
        }
    }
    cout << ans.val << "\n";
}

int main() {
    int n, m, k;
    while(cin >> n >> m >> k, n){
        solve(n, m, k);
    }
    return 0;
}

#line 1 "test/aoj2257.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2257"
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#line 1 "util/modint.cpp"
template <uint M>
struct modint {
    uint val;
public:
    static modint raw(int v) { modint x; x.val = v; return x; }
    modint() : val(0) {}
    template <class T>
    modint(T v) { ll x = (ll)(v%(ll)(M)); if (x < 0) x += M; val = uint(x); }
    modint(bool v) { val = ((unsigned int)(v) % M); }
    modint& operator++() { val++; if (val == M) val = 0; return *this; }
    modint& operator--() { if (val == 0) val = M; val--; return *this; }
    modint operator++(int) { modint result = *this; ++*this; return result; }
    modint operator--(int) { modint result = *this; --*this; return result; }
    modint& operator+=(const modint& b) { val += b.val; if (val >= M) val -= M; return *this; }
    modint& operator-=(const modint& b) { val -= b.val; if (val >= M) val += M; return *this; }
    modint& operator*=(const modint& b) { ull z = val; z *= b.val; val = (uint)(z % M); return *this; }
    modint& operator/=(const modint& b) { return *this = *this * b.inv(); }
    modint operator+() const { return *this; }
    modint operator-() const { return modint() - *this; }
    modint pow(long long n) const { modint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
    modint inv() const { return pow(M-2); }
    friend modint operator+(const modint& a, const modint& b) { return modint(a) += b; }
    friend modint operator-(const modint& a, const modint& b) { return modint(a) -= b; }
    friend modint operator*(const modint& a, const modint& b) { return modint(a) *= b; }
    friend modint operator/(const modint& a, const modint& b) { return modint(a) /= b; }
    friend bool operator==(const modint& a, const modint& b) { return a.val == b.val; }
    friend bool operator!=(const modint& a, const modint& b) { return a.val != b.val; }
};
using mint = modint<MOD>;

/**
 * @brief modint(固定MOD)
 * @docs _md/modint.md
 */
#line 1 "datastructure/ahocorasick.cpp"
template<int W, int start>
class AhoCorasick {
public:
    struct Node {
        array<int, W> to;
        int fail;
        int val;
    };
    explicit AhoCorasick() : v(1) {}
    vector<Node> v;
    vector<int> ord;
    int add(string &s, int cur = 0){
        for (auto &&i : s) {
            if(!v[cur].to[i-start]) v[cur].to[i-start] = v.size(), v.emplace_back();
            cur = v[cur].to[i-start];
        }
        return cur;
    }

    void build() {
        v[0].fail = -1;
        int l = 0, r = 1;
        ord.clear();
        ord.reserve(v.size());
        ord.emplace_back(0);
        while(l < r){
            int i = ord[l]; l++;
            for (int c = 0; c < W; ++c) {
                if(!v[i].to[c]) continue;
                int to = v[i].to[c];
                v[to].fail = (v[i].fail == -1 ? 0 : v[v[i].fail].to[c]);
                ord.emplace_back(to);
                r++;
            }
            if(i != 0){
                for (int c = 0; c < W; ++c) {
                    if(!v[i].to[c]) v[i].to[c] = v[v[i].fail].to[c];
                }
            }
        }
    }
    inline int next(int x, char c){ return v[x].to[c-start]; }
};
/**
 * @brief Aho-Corasick法
 * @docs _md/ahocorasick.md
 */
#line 23 "test/aoj2257.test.cpp"

mint dp[32][501][601][2];
int to[601][501];
int to2[601][501];
int dp0[601];
void solve(int n, int m, int K){
    vector<string> words;
    vector<vector<int>> G;
    fill(dp0, dp0+601, 0);
    vector<string> kigo(K);
    int sz = 0;
    {
        int cur = 0;
        map<string, int> exist;
        for (int i = 0; i < n; ++i) {
            string s, t;
            cin >> s >> t;
            if(!exist.count(s)) {
                exist[s] = cur++;
                words.emplace_back(s);
                G.emplace_back();
            }
            if(!exist.count(t)){
                exist[t] = cur++;
                words.emplace_back(t);
                G.emplace_back();
            }
            G[exist[s]].emplace_back(exist[t]);
        }
        n = words.size();
        AhoCorasick<26, 'a'> aho;
        for (int i = 0; i < K; ++i) {
            cin >> kigo[i];
            dp0[aho.add(kigo[i])]++;
        }
        aho.build();
        for (auto &&i : aho.ord) if(i) dp0[i] += dp0[aho.v[i].fail];
        sz = aho.v.size();
        for (int i = 0; i < sz; ++i) {
            for (int j = 0; j < n; ++j) {
                to[i][j] = i;
                to2[i][j] = 0;
                for (auto &&c : words[j]) {
                    to[i][j] = aho.next(to[i][j], c);
                    to2[i][j] += dp0[to[i][j]];
                }
            }
        }
    }
    for (int i = 0; i < 32; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < sz; ++k) {
                for (int l = 0; l < 2; ++l) {
                    dp[i][j][k][l] = 0;
                }
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if(to2[0][i] < 2) dp[words[i].size()&31][i][to[0][i]][to2[0][i]] += mint(1);
    }
    for (int i = 1; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            for (int k = 0; k < sz; ++k) {
                for (int l = 0; l < 2; ++l) {
                    dp[(i+22)&31][j][k][l] = 0;
                }
            }
        }
        for (int o = 0; o < n; ++o) {
            for (auto &&j : G[o]) {
                if(i+words[j].size() > m) continue;
                int now = i&31, next = (now+words[j].size())&31;
                for (int k = 0; k < sz; ++k) {
                    for (int l = 0; l < 2; ++l) {
                        if(l + to2[k][j] >= 2) continue;
                        dp[next][j][to[k][j]][l+to2[k][j]] += dp[now][o][k][l];
                    }
                }
            }
        }
    }
    mint ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < sz; ++j) {
            ans += dp[m&31][i][j][1];
        }
    }
    cout << ans.val << "\n";
}

int main() {
    int n, m, k;
    while(cin >> n >> m >> k, n){
        solve(n, m, k);
    }
    return 0;
}