WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
BZOJ 5073: 小A的咒语
BZOJ 5073: 小A的咒语

题目大意

给定两个字符串A, B。问将A切成若干段之后,选择不超过X段,按原来次序拼接是否能组成B。

题解

DP[i][k]表示使用了原来字符串A的前i个字符,并且将其切成若干段并选择其中k段,匹配到B字符串的最大长度。
很明显,如果决定进行转移,一定转移能够转移的最大长度,即为A_{i+1, \cdots, n}, B_{dp[i][k]+1, \cdots, m}的最长公共前缀LCP。
所以,如果令v=|LCP(A_{i+1, \cdots, n}, B_{dp[i][k]+1, \cdots, m})|,那么转移方程为:

DP[i+v][k+1]=max(DP[i][k]+v, DP[i+v][k+1])

快速求LCP,我们可以考虑使用后缀自动机+LCA的方法。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;

namespace SAM{
    const int N_CHAR=27;
    const int MAXN=2e5+50;

    struct Node{
        int nxt[N_CHAR], fail;
        int len; // Max Length of State
        int pos; // Appear Position of State, Indexed From 1
        int cnt; // Appear Count of State
    }node[MAXN*2];
    int numn, last, root;

    /**
     * Create New Node for SAM
     */
    inline int newNode(int l, int p){
        int x=++numn;
        for (int i=0; i<N_CHAR; i++) node[x].nxt[i]=0;
        node[x].cnt=node[x].fail=0;
        node[x].len=l;
        node[x].pos=p;
        return x;
    }

    /**
     * Init SAM
     */
    inline void init(){
        root=last=newNode(numn=0, 0);
    }

    /**
     * Add Char Into SAM
     */
    inline int addChar(int c){
        int p=last, np=newNode(node[p].len+1, node[p].len+1);
        while(p && node[p].nxt[c]==0) node[p].nxt[c]=np, p=node[p].fail;
        if (p==0) node[np].fail=root; else{
            int q=node[p].nxt[c];
            if (node[p].len+1 == node[q].len){
                node[np].fail=q;
            }else{
                int nq=newNode(node[p].len+1, node[q].pos);
                for (int i=0; i<N_CHAR; i++) node[nq].nxt[i]=node[q].nxt[i];
                node[nq].fail=node[q].fail;
                node[q].fail=node[np].fail=nq;
                while(p && node[p].nxt[c]==q) node[p].nxt[c]=nq, p=node[p].fail;
            }
        }
        last=np;  node[np].cnt=1;
        return last;
    }
}

namespace LCA{
    const int MAXN=2e5+50;
    const int LOGN=25;
    int dep[MAXN], ver[MAXN*2], rev[MAXN], dfn;
    int Pow2[LOGN], Log2[MAXN*2];
    struct Edge{
        int v, nxt;
        Edge(){}
        Edge(int v0, int n0){ v=v0; nxt=n0; }
    }e[MAXN*2];
    int head[MAXN], nume;

    void dfs(int x, int from){
        dep[x]=dep[from]+1;
        ver[++dfn]=x; rev[x]=dfn;
        for (int i=head[x]; i; i=e[i].nxt){
            int v=e[i].v; if (v==from) continue;
            dfs(v, x); ver[++dfn]=x;
        }
    }

    int dp[MAXN*2][LOGN];
    void st(){
        for (int i=1; i<=dfn; i++) dp[i][0]=ver[i];
        for (int k=1; k<LOGN; k++){
            for (int i=1; i+Pow2[k]-1<=dfn; i++){
                int x=dp[i][k-1], y=dp[i+Pow2[k-1]][k-1];
                dp[i][k]=dep[x]<dep[y]?x:y;
            }
        }
    }
    int rmq(int left, int right){
        int k=Log2[right-left+1];
        int x=dp[left][k], y=dp[right-Pow2[k]+1][k];
        return dep[x]<dep[y]?x:y;
    }

    inline void init(){
        Log2[0]=-1; for (int i=1; i<MAXN*2; i++) Log2[i]=Log2[i>>1]+1;
        Pow2[0]=1; for (int i=1; i<LOGN; i++) Pow2[i]=Pow2[i-1]<<1;
    }

    inline void initEdge(){ memset(head, 0, sizeof(head)); nume=0; }

    inline void addEdge(int u, int v){
        e[++nume]=Edge(v, head[u]);
        head[u]=nume;
        e[++nume]=Edge(u, head[v]);
        head[v]=nume;
    }

    inline void prepare(){ dep[0]=dfn=0; dfs(1, 0); st();}

    inline int query(int u, int v){
        int x=rev[u], y=rev[v];
        if (x>y) swap(x, y);
        return rmq(x, y);
    }
}

const int MAXN=1e5+50;
char str[MAXN];
int idA[MAXN], idB[MAXN];

int n, m, x;
int dp[MAXN][150];
inline int LCP(int x, int y){
    if (x>n || y>m) return 0;
    return SAM::node[LCA::query(idA[x], idB[y])].len;
}
inline void solve(int T){
    SAM::init();
    scanf("%d%d%d", &n, &m, &x);
    scanf("%s", str); reverse(str, str+n);
    for (int i=0; i<n; i++) idA[n-i]=SAM::addChar(str[i]-'a');
    //for (int i=1; i<=n; i++) printf("%d", idA[i]); printf("\n");
    SAM::addChar(26);
    scanf("%s", str); reverse(str, str+m);
    for (int i=0; i<m; i++) idB[m-i]=SAM::addChar(str[i]-'a');
    //for (int i=1; i<=m; i++) printf("%d", idB[i]); printf("\n");


    LCA::initEdge();
    for (int i=2; i<=SAM::numn; i++) LCA::addEdge(i, SAM::node[i].fail);//, printf("%d->%d\n", i, SAM::node[i].fail);
    LCA::prepare();

    memset(dp, -1, sizeof(dp));
    dp[0][0]=0;
    for (int i=0; i<n; i++){
        for (int k=0; k<=x; k++){
            if (dp[i][k]==-1) continue;
            dp[i+1][k]=max(dp[i+1][k], dp[i][k]);
            int v=LCP(i+1, dp[i][k]+1);
            if (v>0) dp[i+v][k+1]=max(dp[i+v][k+1], dp[i][k]+v);
        }
    }

    for (int k=1; k<=x; k++)
        if (dp[n][k]==m) { puts("Yes"); return; }

    puts("No");
}

int main(){
    //freopen("in.txt", "r", stdin);
    LCA::init();
    int T=0; scanf("%d", &T);
    for (int i=1; i<=T; i++) solve(i);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

BZOJ 5073: 小A的咒语
题目大意 给定两个字符串A, B。问将A切成若干段之后,选择不超过X段,按原来次序拼接是否能组成B。 题解 $DP[i][k]$表示使用了原来字符串A的前i个字符,并且将其切成若干段并选择其中k…
扫描二维码继续阅读
2018-10-09
<--! http2https -->