Description

标点符号的出现晚于文字的出现, 所以以前的语言都是没有标点的. 现在你要处理的就是一段没有标点的文章. 一段文章 \(T\) 是由若干小写字母构成. 一个单词 \(W\) 也是由若干小写字母构成. 一个字典 \(D\) 是若干个单词的集合. 我们称一段文章 \(T\) 在某个字典 \(D\) 下是可以被理解的, 是指如果文章 \(T\) 可以被分成若干部分, 且每一个部分都是字典 \(D\) 中的单词. 例如字典 \(D\) 中包括单词 \(\{‘is’, ‘name’, ‘what’, ‘your’\}\), 则文章 \(`whatisyourname'\) 是在字典 \(D\) 下可以被理解的因为它可以分成 \(4\) 个单词:\(‘what’, ‘is’, ‘your’, ‘name’\), 且每个单词都属于字典 \(D\), 而文章 \(‘whatisyouname’\) 在字典 \(D\) 下不能被理解, 但可以在字典 \(D’=D+\{‘you’\}\) 下被理解. 这段文章的一个前缀 \(‘whatis’\), 也可以在字典 \(D\) 下被理解 而且是在字典 \(D\) 下能够被理解的最长的前缀. 给定一个字典 \(D\), 你的程序需要判断若干段文章在字典 \(D\) 下是否能够被理解. 并给出其在字典 \(D\) 下能够被理解的最长前缀的位置.

Input

输入文件第一行是两个正整数 \(n\) 和 \(m\), 表示字典 \(D\) 中有 \(n\) 个单词, 且有 \(m\) 段文章需要被处理. 之后的 \(n\) 行每行描述一个单词, 再之后的 \(m\) 行每行描述一段文章. 其中 \(1 \leq n, m \leq 20\), 每个单词长度不超过 \(10\), 每段文章长度不超过 \(10^6\) 个字节.

Output

对于输入的每一段文章, 你需要输出这段文章在字典 \(D\) 可以被理解的最长前缀的位置.

Sample Input

4 3
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

Sample Output

14
6
0

Explanation

考虑这些单词都比较短, 且 Trie 树的节点数不超过 \(200\) 个, 我们可以直接在树上以文章 \(S\) 为对象, 字典 \(D\) 为转移条件, 跑一遍 DP.

(看到一坨字符串就想到 Trie 或 AC 自动机对不对)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 310, maxm = 2000100;

// class Trie
// {
// public:
    int ncnt, root;
    int ch[maxn][26];
    int dp[maxm];
    bool flag[maxn];
    int make_node(void)
    {
        int p = ncnt++;
        for (int i = 0; i < 26; i++)
            ch[p][i] = 0;
        return p;
    }
    void insert(char str[])
    {
        int p = root;
        for (int i = 0; str[i] != '\0'; i++) {
            int v = str[i] - 'a';
            if (!ch[p][v])
                ch[p][v] = make_node();
            p = ch[p][v];
        }
        flag[p] = true;
        return ;
    }
    int match(char str[])
    {
        int len = strlen(str + 1);
        memset(dp, 0, sizeof(dp));
        dp[0] = true;
        int tmp = 0, res = 0;
        for (int i = 0; i <= len; i++) {
            if (tmp > 10) break;
            if (!dp[i]) {
                tmp += 1;
                continue;
            }
            tmp = 0; res = i;
            // Extending string on length
            for (int j = i + 1, p = ch[root][str[j] - 'a']; p; p = ch[p][str[++j] - 'a']) {
                if (flag[p]) dp[j] = true;
                if (j == len) break;
            }
        }
        return res;
    }
    void init(void)
    {
        ncnt = 0;
        root = make_node();
        return ;
    }
// } tr;

int n, m;
char str[maxm];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    /*tr.*/ init();
    for (int i = 1; i <= n; i++) {
        scanf("%s", str);
        /*tr.*/ insert(str);
    }
    // Matching strings
    for (int i = 1; i <= m; i++) {
        scanf("%s", str + 1);
        int res = /*tr.*/ match(str);
        printf("%d\n", res);
    }
    return 0;
}