워커 연습경기 17B 좋은 자리.DP

1396 단어 DP
제목: 두 줄의 s, x.를 제시하여 i를 좋은 위치로 정의합니다.위치 i를 포함하는 하위 서열이 x와 같습니다.
|s|, |x|<=2e5는 s의 위치가 모두 좋은 위치인지 물어봅니다.
i가 좋은 위치인지 판단하면 접두사 i, 접두사 i+1으로 나눌 수 있다.
s의 접두사 i는 x가 일치하는 위치가 분명히 뒤일수록 좋다.
pre[i]를 접두사 i로 설정하면 최대 몇 개까지 일치할 수 있습니다.f[i]는 위치 i로 끝나는 하위 시퀀스와 최대 몇 개까지 일치합니다.
f[i]<=pre[i], f[i]=x[1:pre[i]]에서 마지막으로 s[i]가 나오는 위치.
그러면 s[i+1:n]에 x[f[i]+1:m]라는 하위 서열이 있습니까? 
s,x를 뒤집어 위와 같이 처리하면 됩니다.
#include 
using namespace std;
const int N=2e5+5;
char s[N],x[N];
int p[N],f[N],suf[N],h[N],n,m;
vector v[30];
int main()
{
	scanf("%s%s",s+1,x+1);
	n=strlen(s+1),m=strlen(x+1);
	for(int i=1;x[i];i++)
		v[x[i]-'a'].push_back(i);
	for(int i=1;s[i];i++)
	{
		int id=s[i]-'a';
		p[i]=p[i-1];
		if(p[i]==m)
		{
			if(v[id].size())
				f[i]=v[id][v[id].size()-1];
		}
		else
		{
			if(x[p[i-1]+1]==s[i])
				p[i]=p[i-1]+1;
			int pos=upper_bound(v[id].begin(),v[id].end(),p[i])-v[id].begin();
			if(pos)
				f[i]=v[id][pos-1];
		}	
	}
	reverse(s+1,s+1+n);
	reverse(x+1,x+1+m);
	for(int i=0;i<30;i++)
		v[i].clear(); 
	for(int i=1;x[i];i++)
		v[x[i]-'a'].push_back(i);
	for(int i=1;s[i];i++)
	{
		int id=s[i]-'a';
		suf[i]=suf[i-1];
		if(s[i]==x[suf[i-1]+1])
			suf[i]++;
	}
	bool flag=true;
	for(int i=1;i<=n;i++)
	{	
		int ned=m-f[i];
		if(suf[n-i]

좋은 웹페이지 즐겨찾기