题解 P2292 【[HNOI2004]L语言】

· · 题解

这道题一眼看去，似乎就是个AC自动机，然后迅速的打出了AC自动机的板子。

最开始思路

最开始我想的是，不就判断一下长度就行了吗，把每一个单词的长度求出来，在AC自动机的时候每次用当前位置的下标减去单词长度，如果小于等于目前的前缀长度，就更新答案，然后迅速地打出代码，发现只有70分，仔细思考了一下，发现是因为我没有读清题目，单词不能有重复，比如如果单词是she element 的话，那么shelement的前缀应该是3，照我这个思路的话算出来是9，所以这个思路还有一些问题。

正确的思路

刚才的思路其实大致方向是没有什么问题的，只需要再多考虑一种情况就是了，接下来该如何考虑这种情况，对于一个最长前缀，我们可以把它划分为许多种不同的单词组成的一个字符串，那么就会有很多种方案，我们只需要将每种方案记录一下即可，那么如何记录？考虑再开一个数组vis，表示是否存在长度为i的合法前缀， 那么这个问题就迎刃而解了。

具体结合代码理解

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 2e6 + 5;

char str[N];
int tr[N][26], cnt[N], net[N], idx;
bool vis[N];
queue<int> q;

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int t = str[i] - 'a';
        if (!tr[p][t])
            tr[p][t] = ++idx;
        p = tr[p][t];
    }
    cnt[p] = strlen(str);//cnt存的是每个单词的长度
}

void build()
{
    for (int i = 0; i < 26; i++)
        if (tr[0][i])
            q.push(tr[0][i]);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
        {
            int p = tr[t][i];
            if (!p)
                tr[t][i] = tr[net[t]][i];
            else 
            {
                net[p] = tr[net[t]][i];
                q.push(p);
            }
        }
    }
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", &str);
        insert();
    }
    build();//AC自动机板子，就不解释了
    while (m--)
    {
        int len = 0;
        memset(vis, 0, sizeof(vis));
        vis[0] = true;//初始化，长度为0的前缀是存在的，所以要标记一下
        scanf("%s", &str);
        for (int i = 0, j = 0; str[i]; i++)
        {
            int t = str[i] - 'a';
            j = tr[j][t];
            int p = j;
            while(p)
            {
                if (vis[i - cnt[p] + 1])//判断之前是否存在一个合法前缀
                {
                    vis[i + 1] = true;//标记一下
                    break;//一个优化，如果找到了就直接退出，不然会T掉最后一个点
                }
                p = net[p];
            }
            if (vis[i + 1])
                len = i + 1;//记录一下答案
        }
        printf("%d\n", len);
    }
    return 0;
}