题解 P1470 【最长前缀 Longest Prefix】

saxiy · 2019-10-21 11:49:05 · 题解

为什么不用 AC\text{自动机} 呢？

其实后面有dalao讲AC自动机，但不是很详细。

我来胡扯一下。。

题目分析：

简意是求在字符串S中，最长能被匹配的前缀长度，多模式串匹配，不就是AC自动机的板子嘛。。

同样要设状态 ok[i] 表示前i位能否被匹配，容易得出转移方程：

上式的\sum表示 逻辑或 运算。

边界条件是 ok[0]=true ，即匹配前0位是一定可以的。

• 在匹配的过程我们使用AC自动机，节点的结束标记可以直接存模式串长度，整个数组就干净了许多，匹配时就暴力跳fail边，匹配到串就根据长度转移状态。

代码实现(21ms in total)：

#include <bits/stdc++.h>
#define N 2010
#define M 200005
using namespace std;

char str[M], msc[N];
int trie[N][26], ed[N], p[N], cnt = 2;
bool ok[M];

void insert(const char* str) {
    int now = 1, len = strlen(str);
    for(int i = 0;i < len;i++) {
        int ch = str[i] - 'A';
        if(!trie[now][ch]) trie[now][ch] = cnt++;
        now = trie[now][ch];
    }
    ed[now] = len;//结束标记 记长度。
}

void pre() {//AC自动机基本操作所以没注释
    for(int ch = 0;ch < 26;ch++)
        trie[0][ch] = 1;
    queue <int> q;
    q.push(1);
    while(q.size()) {
        int now = q.front(); q.pop();
        for(int ch = 0;ch < 26;ch++) {
            if(trie[now][ch]) {
                q.push(trie[now][ch]);
                p[trie[now][ch]] = trie[p[now]][ch];
            } else trie[now][ch] = trie[p[now]][ch];
        }
    }
}

void AC_run(const char* str) {
    *ok = 1;//边界条件
    int now = 1, len = strlen(str + 1);
    for(int i = 1;i <= len;i++) {
        now = trie[now][str[i] - 'A'];
        for(int j = now;j && !ok[i];j = p[j])//暴力跳fail
            if(ed[j]) ok[i] |= ok[i - ed[j]];
            //ok[i]为真就可以break。
    }
    for(int i = len;~i;i--)//找最大匹配位
        if(ok[i]) { printf("%d", i); return; }
}

int main() {
    while(1) {
        scanf("%s", msc);
        if(*msc == '.') break;
        insert(msc);
    }
    pre();
    char *p = str + 1, c;
    //从下标1开始读方便搞边界
    while((c = getchar()) != EOF)
        if('A' <= c && c <= 'Z') *p++ = c;
    *p = '\0';//读入的换行特判^^^^^^^^^^^
    AC_run(str);
    return 0;
}

后记：

这是一道AC自动机板子题。