G. Anthem of Berland

题意：给两串S,T。S由"a-z","?"组成，T由"a-z"组成。你可以钦定这些"?"，询问 T 在 S 中最多出现次数。

想法：考虑Dp，需要记录的是匹配到 T 多长的前缀。于是设$F[i][j]$表示 S 前 j 位现匹配 T 前i位的最多完整匹配次数。转移需要求出$nx[i][v]$表示 T 前i位后面接上v能匹配的最长前缀，用KMP求一下。

Code

#include < cstdio >#include < cstring >#define gec getchar#define FILE(F) freopen(F".in","r",stdin),freopen(F".out","w",stdout)#define DEBUG fprintf(stderr,"Passing [%s] in Line (%d)\n",__FUNCTION__,__LINE__);typedef long long ll;templateinline void read(T&x){	x=0;bool f=0;char c=gec();	for(;c<‘0‘||c>‘9‘;c=gec())f=(c==‘-‘);	for(;c>=‘0‘&&c<=‘9‘;c=gec())x=x*10+c-‘0‘;	x=f?-x:x;}const int MAXN(100010);int lengs,lengt,Ans;char t[MAXN],s[MAXN];namespace KMP{	int next[MAXN],nx[MAXN][26];	void Kmp()	{		int j=0;next[1]=0;		for(int i=2;i<=lengt;i++)		{			while(j&&(t[i]!=t[j+1]||j==lengt))j=next[j];			if(t[i]==t[j+1])j++;			next[i]=j;		}		for(int i=0;i<=lengt;i++)		{			for(int v=0;v<26;v++)			{				int j=i;				while(j&&(v!=t[j+1]-‘a‘||j==lengt))j=next[j];				if(v==t[j+1]-‘a‘)j++;				nx[i][v]=j;			}		}	}	}using namespace KMP;namespace DP{	int N,M;	int max(int a,int b){return a>b?a:b;}	void Dp()	{		N=lengt+10; M=lengs+10;		int F[N][M]; memset(F,128,sizeof(F));		F[0][0]=0;		for(int j=0,Nex;j<lengs;j++)		{			for(int i=0;i<=lengt;i++)			{				if(F[i][j]<0)continue;				if(s[j+1]==‘?‘)				for(int v=0;v<26;v++)				{					Nex=nx[i][v];					F[Nex][j+1]=max(F[Nex][j+1],F[i][j]+(Nex==lengt));				} else				{					Nex=nx[i][s[j+1]-‘a‘];					F[Nex][j+1]=max(F[Nex][j+1],F[i][j]+(Nex==lengt));									}			}		}		for(int i=0;i<=lengt;i++)Ans=max(Ans,F[i][lengs]);	}	}using namespace DP;int main(){#ifndef ONLINE_JUDGE	FILE("C");#endif			scanf("%s",s+1);lengs=strlen(s+1);	scanf("%s",t+1);lengt=strlen(t+1);	if(lengt>lengs){printf("0\n");return 0;}	Kmp(); 	Dp();	printf("%d\n",Ans);	return 0;}

突然迷恋 namespace

Codeforces 808G. Anthem of Berland