[题解] JZOJ – 5795 词典

JZOJ – 5795 词典

Time Limit : 1500ms
Memory Limit : 256MB

Description

Input

第一行两个数 $ n $,$ m $，表示有 $ n $ 个字符串，$ m $ 个询问。
接下来 $ n $ 行，每行一个字符串 $ T_i $ 。
再接下来 $ m $ 行，每行一个字符串 $ S_i $ 。

Output

对于每个询问，输出一个 $ ansi $ 表示答案。

Sample Input

3 2
abcabc
aabc
abbc
aa
ba  

Sample Output

1
3

Data Constraint

解题思路

看到字符串中只包含 $ a $, $ b $, $ c $三个字母且数据随机就能联想到 $ Trie $。

题目要求对于一个字符串 $ S $， 最长有多少个编号连续的 $ T_i $ 不是他的前缀

考虑能否在 $ Trie $ 中直接记录以某个结点为结尾的前缀有多少个编号连续的串不是他的前缀

我们依次将 $ T_i $ 插入 $ Trie $ 中，并用 $ last $ 记录上一个访问此节点的 $ T $ 的编号，那么就有 $ i – last – 1 $ 个编号连续字符串没有经过这个节点，也就意味着不是经过这个节点的串的前缀。

插入的过程中不断以最大值更新答案。最后再用 $ n+1 $ 为 $ last $ 更新一下答案（对应着 $ a $ 数组最后一个 $ 1 $ 到末尾的一段）

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 5000000 + 10;

int Next[MAXN][3], last[MAXN], ans[MAXN], cnt;

inline void add(char *s, int id){
    int length = strlen(s);
    int pos = 0;

    for(register int i=0; i<length; i++){
        int v = s[i] - 'a';

        if(!Next[pos][v]){
            Next[pos][v] = ++cnt;
        }

        ans[pos] = max(ans[pos], id - last[pos] - 1);
        last[pos] = id;

        pos = Next[pos][v];
    }

    ans[pos] = max(ans[pos], id - last[pos] - 1);
    last[pos] = id;
}

int n, m;

inline int query(char *s){
    int length = strlen(s);
    int pos = 0;

    for(register int i=0; i<length; i++){
        int v = s[i] - 'a';

        if(!Next[pos][v]){
            return n;
        }

        pos = Next[pos][v];
    }

    return ans[pos];
}

char input[MAXN];

int main(){

    freopen("word.in", "r", stdin);
    freopen("word.out", "w", stdout);

    scanf("%d%d", &n, &m);

    for(register int i=1; i<=n; i++){
        scanf("%s", input);
        add(input, i);
    }

    for(register int i=1; i<=cnt; i++){
        ans[i] = max(ans[i], n - last[i]);
    }

    for(register int i=1; i<=m; i++){
        scanf("%s", input);
        printf("%d\n", query(input));
    }

    return 0;
}