【luoguP4112】[HEOI2015]最短不公共子串

一个序列自动机+后缀自动机的模板好题
首先第一问和第二问就是送分的,枚举a串的起点,将后缀完全插入进两个自动机,看是否能走到一个空节点就行了。
第三问和第四问是一样的,我们设dp_{i,j}表示目前考虑了a串的前i个字符,走到了自动机j号节点的最短子序列长度即可。
然后方程就是
dp_{i,j}=min(dp_{i-1,j},dp_{i-1,from}+1)这样的东西
然后直接在两个自动机上做dp就可以了。可是我傻子不会第三四问

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

template <typename int_qwq>

inline void re(int_qwq &x)
{
    x = 0;
    char a;
    bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b)
        x = -x;
}

const int ms = 4020;

char a[ms], b[ms];

int n, m, dp[2020][ms];

struct Sam
{
    int ch[ms][26], len[ms], fa[ms], las, cnt;

    inline void insert(int c)
    {
        int p = ++ cnt; len[p] = len[las + 1];
        while(las && (!ch[las][c]))
            ch[las][c] = p, las = fa[las];
        if(!las)
            fa[p] = 1;
        else
        {
            int x = ch[las][c];
            if(len[x] == len[las] + 1)
                fa[p] = x;
            else
            {
                int q = ++ cnt; memcpy(ch[q], ch[x], sizeof(ch[x]));
                len[q] = len[las] + 1, fa[q] = fa[x], fa[x] = fa[p] = q;
                while(las && ch[las][c] == x)
                    ch[las][c] = q, las = fa[las];
            }
        }
        las = p;
    }
}sam;

struct Lam
{
    int cnt, ch[ms][26], las[26];

    inline void insert(int c)
    {
        int no = ++ cnt;
        for(ri i = 0; i < 26; i ++)
            ch[no][i] = las[i];
        las[c] = no;
    }

    inline void init()
    {
        for(ri i = 0; i < 26; i ++)
            ch[1][i] = las[i];
    }
}lam;

inline void ask1()
{
    int pri = 1e9 + 7;
    for(ri i = 1, j; i <= n; i ++)
    {
        int no = 1, ci = 0;
        for(j = i; j <= n; j ++)
        {
            ci ++;
            if(!sam.ch[no][a[j] - 'a'])
                break;
            no = sam.ch[no][a[j] - 'a'];
        }
        if(j <= n)
            pri = min(pri, ci);
    }
    if(pri == 1e9 + 7)
        puts("-1");
    else
        printf("%d\n", pri);
}

inline void ask2()
{
    int pri = 1e9 + 7;
    for(ri i = 1, j; i <= n; i ++)
    {
        int no = 1, ci = 0;
        for(j = i; j <= n; j ++)
        {
            ci ++;
            if(!lam.ch[no][a[j] - 'a'])
                break;
            no = lam.ch[no][a[j] - 'a'];
        }
        if(j <= n)
            pri = min(pri, ci);
    }
    if(pri == 1e9 + 7)
        puts("-1");
    else
        printf("%d\n", pri);
}

inline void ask3()
{
    memset(dp, 63, sizeof(dp));
    dp[0][1] = 0;
    for(ri i = 1; i <= n; i ++)
    {
        for(ri j = 1; j <= sam.cnt; j ++)
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
        for(ri j = 1; j <= sam.cnt; j ++)
        {
            int to = sam.ch[j][a[i] - 'a'];
            dp[i][to] = min(dp[i][to], min(dp[i - 1][to], dp[i - 1][j] + 1));
        }
    }
    if(dp[n][0] == dp[n + 1][0])
        puts("-1");
    else
        printf("%d\n", dp[n][0]);
}

inline void ask4()
{
    memset(dp, 63, sizeof(dp));
    dp[0][1] = 0;
    for(ri i = 1; i <= n; i ++)
    {
        for(ri j = 1; j <= lam.cnt; j ++)
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
        for(ri j = 1; j <= lam.cnt; j ++)
        {
            int to = lam.ch[j][a[i] - 'a'];
            dp[i][to] = min(dp[i][to], min(dp[i - 1][to], dp[i - 1][j] + 1));
        }
    }
    if(dp[n][0] == dp[n + 1][0])
        puts("-1");
    else
        printf("%d\n", dp[n][0]);
}

int main()
{
    scanf("%s%s", a + 1, b + 1);
    n = strlen(a + 1), m = strlen(b + 1);
    sam.las = 1, sam.cnt = 1, lam.cnt = 1;
    for(ri i = 1; i <= m; i ++)
        sam.insert(b[i] - 'a');
    for(ri i = m; i; i --)
        lam.insert(b[i] - 'a');
    lam.init();
    ask1(), ask2(), ask3(), ask4();
    system("pause");
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注