P5231 [JSOI2012]玄武密码

P5231 [JSOI2012]玄武密码

求一个串 $t$ 在另一个串 $s$ 的所有子串中最大的匹配长度。

查看代码

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10;
struct Node
{
    int len, fa;
    int nxt[4];
} tr[N << 1];
char str[N];
int n, m, last = 1, cnt = 1;
int insert(int c)
{
    int p = last, np = ++cnt;
    tr[np].len = tr[p].len + 1;
    for (; p && !tr[p].nxt[c]; p = tr[p].fa)
        tr[p].nxt[c] = np;
    last = cnt;
    if (!p)
    {
        tr[np].fa = 1;
        return np;
    }
    int q = tr[p].nxt[c];
    if (tr[q].len == tr[p].len + 1)
    {
        tr[np].fa = q;
        return np;
    }
    int nq = ++cnt;
    tr[nq] = tr[q], tr[nq].len = tr[p].len + 1;
    tr[q].fa = tr[np].fa = nq;
    for (; p && tr[p].nxt[c] == q; p = tr[p].fa)
        tr[p].nxt[c] = nq;
    return np;
}
int num(char c)
{
    if (c == 'E')
        return 0;
    if (c == 'S')
        return 1;
    if (c == 'W')
        return 2;
    return 3;
}
int main()
{
    scanf("%d%d%s", &n, &m, str + 1);
    for (int i = 1; i <= n; i++)
        insert(num(str[i]));
    for (int p = 1; m; m--, p = 1)
    {
        scanf("%s", str + 1);
        n = strlen(str + 1);
        for (int i = 0; i <= n; i++)
        {
            int t = tr[p].nxt[num(str[i + 1])];
            if (i == n || !t)
            {
                printf("%d\n", i);
                break;
            }
            p = t;
        }
    }
    return 0;
}