题解 P5826 【【模板】子序列自动机】
_虹_
2019-12-18 09:57:00
[基本不更新的博客](https://www.luogu.com.cn/blog/RainbowCat/)
提供一个离线O(∑L)做法。
双倍经验，双倍快乐[P3500](https://www.luogu.com.cn/problem/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;
}
```