Noble 的博客

Noble 的博客

♡虹蓝♡

题解 P5826 【【模板】子序列自动机】

posted on 2019-12-18 09:57:00 | under 题解 |

基本不更新的博客

提供一个离线O(∑L)做法。

双倍经验,双倍快乐P3500

首先看一下这题是如何匹配的。

对于文本串A,模式串B已经匹配i位,第i位匹配文本串位置为x,第i+1位为j。

假设存在x<a<b,A(a)==A(b)==j,则第i+1位匹配a位置显然不劣于b位置。

换句话说就是贪心的能匹配就一定匹配。

设函数f(i-1,j)为询问j,考虑完文本串前i-1个字符后,当前未匹配的首个字符。

则对于所有f(i-1,j)==A(i)的j,全部都完成了该字符的匹配,f(i,j)=next(j)。对于不相等的,则有f(i,j)=f(i-1,j)

显然f函数第一维其实没啥用,完全可以删去。

所以直接按照待匹配字符(即f函数)对询问分类,扫描文本串,每次处理等待匹配该字符的询问就行了。

具体实现可以用双向链表或单向链表,这里选择了白嫖std::list

#include <iostream>
#include <list>
using namespace std;
const int kmaxn=1000000+5;
int arr[kmaxn];
int ask[kmaxn];
int len[kmaxn];
int pos[kmaxn];
int tar[kmaxn];
list<int> lst[kmaxn];
int n,m,q,t;
int main()
{
    ios::sync_with_stdio(false);
    cin>>t>>n>>q>>m;
    for(int i=1;i<=n;++i)
        cin>>arr[i];
    for(int i=1,m=0;i<=q;++i)
    {
        cin>>len[i];
        for(int j=1,k=len[i];j<=k;++j)
            cin>>ask[++m];
        tar[i]=m+1;
        lst[ask[pos[i]=m-len[i]+1]].push_front(i);
    }
    for(int i=1;i<=n;++i)
    {
        m=lst[arr[i]].size();
        while(m--)
        {
            t=*lst[arr[i]].begin();
            lst[arr[i]].pop_front();
            if((++pos[t])!=tar[t])
                lst[ask[pos[t]]].push_back(t);
        }
    }
    for(int i=1;i<=q;++i)
        cout<<(pos[i]==tar[i]?"Yes\n":"No\n");
    return 0;
}