题解 P4584 【[FJOI2015]带子串包含约束LCS问题】

· · 题解

好像还没有题解？来简要的写一下一篇不会证明的题解

我们可以把题目转化成两个不同的问题然后进行合并

第一个问题： 我们发现要求的是多串问题，然后这些串都要同时出现在一个串内，所以我们可以建出ac自动机，然后发现k<=6，因此可以状压出有没有出现过的状态，并且记录当前所在节点

第二个问题： 我们要求这个串是给出的两个串的公共子序列，然后这个我们可以考虑这是一个子序列自动机的裸题，只需要建出子序列自动机然后在自动机上遍历即可，记录在两个串上当前的位置就好了

所以综上所述要记录四个状态，第一个问题的两个和第二个问题的两个串的出现位置 我们发现这些状态之间的转移像是一个拓扑图，然后最长路转移就好了

然后发现状态数用数组记录不下，所以要用map，具体状态数不会太大（感性理解） 复杂度：O(能过)

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

const int N = 1805;

int n, m, k, ch[N][52], tot, fail[N], ed[N], ans;
int tsx[305][52], tsy[305][52], l[N], lst[52];
char strx[305], stry[305], str[305];

struct node {
    int px, py, u, mask;
    node(int cpx = 0, int cpy = 0, int cu = 0, int cmask = 0) {
        px = cpx, py = cpy, u = cu, mask = cmask;
    }
    bool operator < (const node &c) const {
        if (px != c.px) return px < c.px;
        if (py != c.py) return py < c.py;
        if (u != c.u) return u < c.u;
        return mask < c.mask;
    }
};
map<node, int> stp; map<node, bool> inq;

int Type(char c) {
    if (c >= 'a' && c <= 'z') return c - 'a';
    return c - 'A' + 26;
}

#define SS ch[u][i]
void BFS() {
    queue<int> que; while (!que.empty()) que.pop();
    for (int i = 0; i < 52; i++) if (ch[0][i]) que.push(ch[0][i]);
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = 0; i < 52; i++)
            if (!SS) SS = ch[fail[u]][i];
            else que.push(SS), fail[SS] = ch[fail[u]][i], ed[SS] |= ed[fail[SS]];
    }
}

void DP() {
    queue<node> que; while (!que.empty()) que.pop();
    stp[node(0, 0, 0, 0)] = 1; que.push(node(0, 0, 0, 0)), inq[node(0, 0, 0, 0)] = true;
    while (!que.empty()) {
        node now = que.front(); que.pop(); inq[now] = false;
        int ntp = stp[now];
        int px = now.px, py = now.py, u = now.u, mask = now.mask;
        if (mask == (1 << k) - 1) ans = max(ans, ntp);
        for (int i = 0; i < 52; i++) {
            int nx = tsx[px][i], ny = tsy[py][i], v = ch[u][i], nsk = mask | ed[v];
            if (nx > n || ny > m) continue; node to = node(nx, ny, v, nsk);
            if (!stp[to] || stp[to] < ntp + 1) {
                stp[to] = ntp + 1;
                if (!inq[to]) que.push(to);
            }
        }
    }
}

int main() {
    n = read(); m = read(); k = read();
    for (int i = 1; i <= k; i++) l[i] = read();
    scanf("%s", strx + 1), scanf("%s", stry + 1);
    for (int i = 0; i < 52; i++) lst[i] = n + 1;
    for (int i = n; i >= 0; i--) {
        for (int j = 0; j < 52; j++) tsx[i][j] = lst[j];
        lst[Type(strx[i])] = i;
    }
    for (int i = 0; i < 52; i++) lst[i] = m + 1;
    for (int i = m; i >= 0; i--) {
        for (int j = 0; j < 52; j++) tsy[i][j] = lst[j];
        lst[Type(stry[i])] = i;
    }
    for (int i = 1; i <= k; i++) {
        scanf("%s", str + 1); int u = 0;
        for (int j = 1; j <= l[i]; j++) {
            int p = Type(str[j]);
            if (!ch[u][p]) ch[u][p] = ++tot;
            u = ch[u][p];
        }
        ed[u] |= (1 << i - 1);
    }
    BFS(), DP();
    printf("%d\n", ans - 1);
    return 0;
}