P1470 [USACO2.3] Longest Prefix 题解

wxzzzz · 2023-07-21 10:00:16 · 个人记录

题意

求用一堆小字符串能拼出 s 最长前缀的长度（可以重复使用）。

思路

前置：KMP。

先用 KMP 求出在 s 中每个出现过小字符串的位置，以及相应的小字符串的长度，然后以出现位置为第一关键字排序，这样我们就得到了一些类似于线段的数据，然后，把这些线段合并，左端点为 1 的最长线段长度即是答案。

最后特判一下，如果没有任何线段的左端点为 1，则无解，输出 0。

代码

#include <bits/stdc++.h>
using namespace std;
int t, n, m, cnt, ans, now, cntp, lent, len[10000005], nxt[15];
char s[10000005], c[10000005], tmp[10000005], st[10000005][15];
struct node {
    int id, len;
} pos[10000005];
inline bool cmp(node x, node y) {
    if (x.id == y.id)
        return x.len < y.len;

    return x.id < y.id;
}
inline void solve(char p[]) {
    m = strlen(p + 1);
    memset(nxt, 0, sizeof nxt);

    for (int i = 2, j = 0; i <= m; i++) {
        while (j && p[j + 1] != p[i])
            j = nxt[j];

        if (p[j + 1] == p[i])
            j++;

        nxt[i] = j;
    }
}
inline void mate(char p[]) {
    m = strlen(p + 1);

    for (int i = 1, j = 0; i <= n; i++) {
        while (j && s[i] != p[j + 1])
            j = nxt[j];

        if (s[i] == p[j + 1])
            j++;

        if (j == m)
            pos[++cntp].id = i - m + 1, pos[cntp].len = m, j = nxt[j];
    }
}
int main() {
    while (1) {
        scanf("%s", c + 1);

        if (c[1] == '.')
            break;

        t = strlen(c + 1), cnt++;

        for (int i = 1; i <= t; i++) {
            st[cnt][i] = c[i];
        }
    }

    while (~scanf("%s", tmp + 1)) {
        lent = strlen(tmp + 1);

        for (int i = 1; i <= lent; i++) {
            s[++n] = tmp[i];
        }
    }

    for (int i = 1; i <= cnt; i++) {
        solve(st[i]), mate(st[i]);
    }

    sort(pos + 1, pos + 1 + cntp, cmp);

    if (pos[1].id > 1) {
        cout << 0;
        return 0;
    }

    for (int i = 1; i <= cntp; i++) {
        if (pos[i].id <= now + 1) {
            now = max(now, pos[i].id + pos[i].len - 1);
        }
    }

    cout << min(now, n);
    return 0;
}