Description

人们在英文字典中查找某个单词的时候可能不知道该单词的完整拼法, 而只知道该单词的一个错误的近似拼法, 这时人们可能陷入困境, 为了查找一个单词而浪费大量的时间. 带有模糊查询功能的电子字典能够从一定程度上解决这一问题: 用户只要输入一个字符串, 电子字典就返回与该单词编辑距离最小的几个单词供用户选择.

字符串 \(a\) 与字符串 \(b\) 的编辑距离是指: 允许对 \(a\) 或 \(b\) 串进行下列 “编辑” 操作, 将 \(a\) 变为 \(b\) 或 \(b\) 变为 \(a\), 最少 “编辑” 次数即为距离.

  • 删除串中某个位置的字母
  • 添加一个字母到串中某个位置
  • 替换串中某一位置的一个字母为另一个字母

JSOI 团队正在开发一款电子字典, 你需要帮助团队实现一个用于模糊查询功能的计数部件: 对于一个待查询字符串, 如果它是单词, 则返回 \(-1\); 如果它不是单词, 则返回字典中有多少个单词与它的编辑距离为 \(1\).

Input

第一行包含两个正整数 \(n\) 和 \(m\).

接下来的 \(n\) 行, 每行一个字符串, 第 \(i+1\) 行为单词 \(W_i\). 单词长度在 \(1\) 至 \(20\) 之间.

再接下来 \(m\) 行, 每行一个字符串, 第 \(i+n+1\) 表示一个待查字符串 \(Q_i\). 待查字符串长度在 \(1\) 至 \(20\) 之间.

\(W_i\) 和 \(Q_i\) 均由小写字母构成, 文件中不包含多余空格. 所有单词互不相同, 但是查询字符串可能有重复.

Output

输出应包括 \(m\) 行, 第 \(i\) 行为一个整数 \(X_i\).\(X_i = -1\) 表示 \(Q_i\) 为字典中的单词; 否则 \(X_i\) 表示与 \(Q_i\) 编辑距离为 \(1\) 的单词的个数.

Sample Input

4 3
abcd
abcde
aabc
abced
abcd
abc
abcdd

Sample Output

-1
2
3

Data Range

对于 50% 的数据, 满足:\(n \leq 1000, m \leq 1000\);

对于所有数据, 满足:\(n \leq 10000, m \leq 10000\).

Explanation

查询的方法很类似朴素的 Trie 树, 并且也不需要 fail 指针, 我也不清楚为什么我的类名启成了 AhoCorasickAutomaton.

在查询的时候适当转移, 添加字符、删除字符以及修改字符, 适当考虑孩子节点状况即可作出类似 Trie 树的查询. 否则维护数量返回数量.

大概就是一棵魔改版 Trie 树......

Source Code


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

using namespace std;
typedef long long lli;
const int maxn = 200100;

class AhoCorasickAutomaton
{
public:
    int ch[maxn][26];
    bool flag[maxn], vis[maxn];
    int root, ncnt;
    void insert(char str[])
    {
        int len = strlen(str),
            p = root;
        for (int i = 0; i < len; i++) {
            int v = str[i] - 'a';
            if (!ch[p][v])
                ch[p][v] = ++ncnt;
            p = ch[p][v];
        }
        flag[p] = true;
        return ;
    }
    queue<int> que;
    int dfs(char str[], int len, int p, int pos, int offset)
    {
        if (pos == len && flag[p] && offset == 0)
            return 0;
        if (pos == len && flag[p] && offset != 0) {
            if (vis[p])
                return 0;
            que.push(p);
            vis[p] = true;
            return 1;
        }
        int sum = 0;
        // Supposing that this character is removed
        if (pos < len && offset == 0)
            sum += dfs(str, len, p, pos + 1, 1);
        // Supposing that this character is modified
        if (offset == 0) {
            for (int i = 0; i < 26; i++)
                if (ch[p][i])
                    sum += dfs(str, len, ch[p][i], pos, 1);
            // Or continue with addition
            for (int i = 0; i < 26; i++)
                if (ch[p][i] && i != str[pos+1] - 'a')
                    sum += dfs(str, len, ch[p][i], pos + 1, 1);
        }
        // Can't just add something...
        if (pos < len && ch[p][str[pos+1]-'a'])
            sum += dfs(str, len, ch[p][str[pos+1]-'a'], pos + 1, offset);
        // Returns
        return sum;
    }
    int query(char str[])
    {
        // Finding if this is a string in the tree
        bool found = true;
        int len = strlen(str + 1),
            p = root;
        for (int i = 1; i <= len; i++) {
            int v = str[i] - 'a';
            if (!ch[p][v]) {
                found = false;
                break;
            }
            p = ch[p][v];
        }
        if (found && flag[p])
            return -1;
        // Depth First Search
        while (!que.empty()) {
            vis[que.front()] = false;
            que.pop();
        }
        return dfs(str, len, root, 0, 0);
    }
    void init(void)
    {
        ncnt = 0;
        root = ++ncnt;
        return ;
    }
} acm;

int n, m;
char str[64];

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