Ideone.com

fork download

copy

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
#define pii pair <int, int>
#define fi first
#define se second
#define all(ac) ac.begin(), ac.end()
#define MASK(x) (1LL << x)
#define ub(i, j) ((i >> j) & 1)
 
string dic[26] = {
    ".-","-...","-.-.","-..",".","..-.","--.","....","..",".---",
    "-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-",
    "..-","...-",".--","-..-","-.--","--.."
};
 
string Morse(const string &s) {
    string t;
    for(char ch: s) t += dic[ch - 'A'];
    return t; 
}
 
struct AhoCorasick {
    struct Node {
        int child[2];
        int link;
        int apr, high;
 
        Node(): link(0), apr(0), high(0) {
            memset(child, 0, sizeof child);
        }
    };
 
    vector <Node> node;
 
    AhoCorasick() {
        node = {Node()};
    }
 
    int newnode() {
        node.eb(Node());
        return (int) node.size() - 1;
    }
 
    void insert(const string &s) {
        int u = 0;
        for(char ch: s) {
            int c = ch - 45;
            if(!node[u].child[c]) {
                node[u].child[c] = newnode();
                node[node[u].child[c]].high = node[u].high + 1;
            }
            u = node[u].child[c];
        }
        node[u].apr++;
        return;
    }
 
    void Build() {
        queue <int> Q;
        for(int i=0;i<2;i++) if(node[0].child[i]) {
            Q.emplace(node[0].child[i]);
        }
 
        while(Q.size()) {
            int u = Q.front();
            int v = node[u].link;
            Q.pop();
 
            for(int i=0;i<2;i++) {
                if(!node[u].child[i]) node[u].child[i] = node[v].child[i];
                else {
                    Q.emplace(node[u].child[i]);
                    node[node[u].child[i]].link = node[v].child[i];
                }
            }
        }
        return;
    }
 
    int Process(string &s) {
        int n = s.size();
        int dp[n + 1];
        memset(dp, 0, sizeof dp);
        dp[0] = 1;
        int it = 0;
        s = " " + s;
        for(int i=1;i<=n;i++) {
            int c = s[i] - 45;
            it = node[it].child[c];
            int tmp = it;
            do {
                int sz = node[tmp].high;
                if(sz <= i) dp[i] += dp[i - sz] * node[tmp].apr;
                tmp = node[tmp].link;
            } while(tmp > 0);
        }
        return dp[n];
    }
};
 
void solve() {
    AhoCorasick aho;
    string s; cin >> s;
    int n; cin >> n;
    for(int i=1;i<=n;i++) {
        string t; cin >> t;
        aho.insert(Morse(t));
    }
 
    aho.Build();
 
    cout << aho.Process(s) << '\n';
    return;
}
 
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    #define task "tet"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
 
    int testcase; cin >> testcase;
    while(testcase--) solve();
    return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgZWIgZW1wbGFjZV9iYWNrCiNkZWZpbmUgcGlpIHBhaXIgPGludCwgaW50PgojZGVmaW5lIGZpIGZpcnN0CiNkZWZpbmUgc2Ugc2Vjb25kCiNkZWZpbmUgYWxsKGFjKSBhYy5iZWdpbigpLCBhYy5lbmQoKQojZGVmaW5lIE1BU0soeCkgKDFMTCA8PCB4KQojZGVmaW5lIHViKGksIGopICgoaSA+PiBqKSAmIDEpCgpzdHJpbmcgZGljWzI2XSA9IHsKICAgICIuLSIsIi0uLi4iLCItLi0uIiwiLS4uIiwiLiIsIi4uLS4iLCItLS4iLCIuLi4uIiwiLi4iLCIuLS0tIiwKICAgICItLi0iLCIuLS4uIiwiLS0iLCItLiIsIi0tLSIsIi4tLS4iLCItLS4tIiwiLi0uIiwiLi4uIiwiLSIsCiAgICAiLi4tIiwiLi4uLSIsIi4tLSIsIi0uLi0iLCItLi0tIiwiLS0uLiIKfTsKCnN0cmluZyBNb3JzZShjb25zdCBzdHJpbmcgJnMpIHsKICAgIHN0cmluZyB0OwogICAgZm9yKGNoYXIgY2g6IHMpIHQgKz0gZGljW2NoIC0gJ0EnXTsKICAgIHJldHVybiB0OyAKfQoKc3RydWN0IEFob0NvcmFzaWNrIHsKICAgIHN0cnVjdCBOb2RlIHsKICAgICAgICBpbnQgY2hpbGRbMl07CiAgICAgICAgaW50IGxpbms7CiAgICAgICAgaW50IGFwciwgaGlnaDsKICAgICAgICAKICAgICAgICBOb2RlKCk6IGxpbmsoMCksIGFwcigwKSwgaGlnaCgwKSB7CiAgICAgICAgICAgIG1lbXNldChjaGlsZCwgMCwgc2l6ZW9mIGNoaWxkKTsKICAgICAgICB9CiAgICB9OwoKICAgIHZlY3RvciA8Tm9kZT4gbm9kZTsKICAgIAogICAgQWhvQ29yYXNpY2soKSB7CiAgICAgICAgbm9kZSA9IHtOb2RlKCl9OwogICAgfQoKICAgIGludCBuZXdub2RlKCkgewogICAgICAgIG5vZGUuZWIoTm9kZSgpKTsKICAgICAgICByZXR1cm4gKGludCkgbm9kZS5zaXplKCkgLSAxOwogICAgfQoKICAgIHZvaWQgaW5zZXJ0KGNvbnN0IHN0cmluZyAmcykgewogICAgICAgIGludCB1ID0gMDsKICAgICAgICBmb3IoY2hhciBjaDogcykgewogICAgICAgICAgICBpbnQgYyA9IGNoIC0gNDU7CiAgICAgICAgICAgIGlmKCFub2RlW3VdLmNoaWxkW2NdKSB7CiAgICAgICAgICAgICAgICBub2RlW3VdLmNoaWxkW2NdID0gbmV3bm9kZSgpOwogICAgICAgICAgICAgICAgbm9kZVtub2RlW3VdLmNoaWxkW2NdXS5oaWdoID0gbm9kZVt1XS5oaWdoICsgMTsKICAgICAgICAgICAgfQogICAgICAgICAgICB1ID0gbm9kZVt1XS5jaGlsZFtjXTsKICAgICAgICB9CiAgICAgICAgbm9kZVt1XS5hcHIrKzsKICAgICAgICByZXR1cm47CiAgICB9CgogICAgdm9pZCBCdWlsZCgpIHsKICAgICAgICBxdWV1ZSA8aW50PiBROwogICAgICAgIGZvcihpbnQgaT0wO2k8MjtpKyspIGlmKG5vZGVbMF0uY2hpbGRbaV0pIHsKICAgICAgICAgICAgUS5lbXBsYWNlKG5vZGVbMF0uY2hpbGRbaV0pOwogICAgICAgIH0KCiAgICAgICAgd2hpbGUoUS5zaXplKCkpIHsKICAgICAgICAgICAgaW50IHUgPSBRLmZyb250KCk7CiAgICAgICAgICAgIGludCB2ID0gbm9kZVt1XS5saW5rOwogICAgICAgICAgICBRLnBvcCgpOwoKICAgICAgICAgICAgZm9yKGludCBpPTA7aTwyO2krKykgewogICAgICAgICAgICAgICAgaWYoIW5vZGVbdV0uY2hpbGRbaV0pIG5vZGVbdV0uY2hpbGRbaV0gPSBub2RlW3ZdLmNoaWxkW2ldOwogICAgICAgICAgICAgICAgZWxzZSB7CiAgICAgICAgICAgICAgICAgICAgUS5lbXBsYWNlKG5vZGVbdV0uY2hpbGRbaV0pOwogICAgICAgICAgICAgICAgICAgIG5vZGVbbm9kZVt1XS5jaGlsZFtpXV0ubGluayA9IG5vZGVbdl0uY2hpbGRbaV07CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcmV0dXJuOwogICAgfQoKICAgIGludCBQcm9jZXNzKHN0cmluZyAmcykgewogICAgICAgIGludCBuID0gcy5zaXplKCk7CiAgICAgICAgaW50IGRwW24gKyAxXTsKICAgICAgICBtZW1zZXQoZHAsIDAsIHNpemVvZiBkcCk7CiAgICAgICAgZHBbMF0gPSAxOwogICAgICAgIGludCBpdCA9IDA7CiAgICAgICAgcyA9ICIgIiArIHM7CiAgICAgICAgZm9yKGludCBpPTE7aTw9bjtpKyspIHsKICAgICAgICAgICAgaW50IGMgPSBzW2ldIC0gNDU7CiAgICAgICAgICAgIGl0ID0gbm9kZVtpdF0uY2hpbGRbY107CiAgICAgICAgICAgIGludCB0bXAgPSBpdDsKICAgICAgICAgICAgZG8gewogICAgICAgICAgICAgICAgaW50IHN6ID0gbm9kZVt0bXBdLmhpZ2g7CiAgICAgICAgICAgICAgICBpZihzeiA8PSBpKSBkcFtpXSArPSBkcFtpIC0gc3pdICogbm9kZVt0bXBdLmFwcjsKICAgICAgICAgICAgICAgIHRtcCA9IG5vZGVbdG1wXS5saW5rOwogICAgICAgICAgICB9IHdoaWxlKHRtcCA+IDApOwogICAgICAgIH0KICAgICAgICByZXR1cm4gZHBbbl07CiAgICB9Cn07Cgp2b2lkIHNvbHZlKCkgewogICAgQWhvQ29yYXNpY2sgYWhvOwogICAgc3RyaW5nIHM7IGNpbiA+PiBzOwogICAgaW50IG47IGNpbiA+PiBuOwogICAgZm9yKGludCBpPTE7aTw9bjtpKyspIHsKICAgICAgICBzdHJpbmcgdDsgY2luID4+IHQ7CiAgICAgICAgYWhvLmluc2VydChNb3JzZSh0KSk7CiAgICB9CgogICAgYWhvLkJ1aWxkKCk7CgogICAgY291dCA8PCBhaG8uUHJvY2VzcyhzKSA8PCAnXG4nOwogICAgcmV0dXJuOwp9CgppbnQzMl90IG1haW4oKSB7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKDApLCBjb3V0LnRpZSgwKTsKICAgICNkZWZpbmUgdGFzayAidGV0IgogICAgaWYoZm9wZW4odGFzayIuaW5wIiwgInIiKSkgewogICAgICAgIGZyZW9wZW4odGFzayIuaW5wIiwgInIiLCBzdGRpbik7CiAgICAgICAgZnJlb3Blbih0YXNrIi5vdXQiLCAidyIsIHN0ZG91dCk7CiAgICB9CgogICAgaW50IHRlc3RjYXNlOyBjaW4gPj4gdGVzdGNhc2U7CiAgICB3aGlsZSh0ZXN0Y2FzZS0tKSBzb2x2ZSgpOwogICAgcmV0dXJuIDA7Cn0=

Success #stdin #stdout 0.01s 5248KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/GnORGl

language:

C++ (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language