「题解报告」 P3167 [CQOI2014]通配符匹配

思路

*和?显然无法直接匹配，但是可以发现「通配符个数不超过 \(10\) 」，那么我们可以考虑分段匹配。

我们首先把原字符串分成多个以一个通配符开头的字符串，如将 happy*birthdey?xingchen 分成：

happy

*birthday

?xingchen

然后设原串有 \(m\) 个通配符， \(op_i\) 表示分出来的第 \(i\) 个串前的通配符（\(0\) 没有，\(1\) 是?，\(2\) 是*），\(len_i\) 表示分出来的第 \(i\) 个串的长度，\(f_{i,j}\) 表示分出来的第 \(i\) 个串的结尾能否匹配上当前查询的字符串的位置 \(j\)。

则转移方程显然为：

\[f_{i,j}=
\begin{cases}
f_{i-1,j-len_i}&op_i=0\\
f_{i-1,j-len_i-1}&op_i=1\\
\sum_{k=0}^{j-len}f_{i-1,j-len_i}&op_i=2\\
\end{cases}
\]

能否转移直接用 Hash \(\Theta(1)\) 比较即可。

初始状态 \(f_{0,0}=1\)，答案为 \(f_{m,\left|S\right|}\)，时间复杂度 \(\Theta(mn\left|S\right|)\)。

代码

const ll N=1e5+10,inf=1ll<<40;

ll T,n,m=1,ln,ans;

ll a1[20],a2[20],len[20],op[20];

ll f[20][N],sm[N];

char s[N],t[N];

class Hash{

public:

	const ll P1=315716521,P2=475262633;

	ll h1[N],h2[N],z1[N],z2[N];

	inline void Init(char *s){

		z1[0]=z2[0]=1;

		ll length=strlen(s+1);

		_for(i,1,length){

			z1[i]=z1[i-1]*233%P1;

			z2[i]=z2[i-1]*233%P2;

			h1[i]=(h1[i-1]*233+s[i]-'a'+1)%P1;

			h2[i]=(h2[i-1]*233+s[i]-'a'+1)%P2;

		}

		return;

	}

	inline ll GetHash1(ll l,ll r){return (h1[r]-h1[l-1]*z1[r-l+1]%P1+P1)%P1;}

	inline ll GetHash2(ll l,ll r){return (h2[r]-h2[l-1]*z2[r-l+1]%P2+P2)%P2;}

}b;

namespace SOLVE{

	inline ll rnt(){

		ll x=0,w=1;char c=getchar();

		while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}

		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();

		return x*w;

	}

	inline ll GetA1(char *awa){

		ll hash_val=0;

		ll length=strlen(awa+1);

		_for(i,1,length)hash_val=(hash_val*233+awa[i]-'a'+1)%b.P1;

		return hash_val;

	}

	inline ll GetA2(char *awa){

		ll hash_val=0;

		ll length=strlen(awa+1);

		_for(i,1,length)hash_val=(hash_val*233+awa[i]-'a'+1)%b.P2;

		return hash_val;

	}

	inline void Pre(){

		char qwq[N];

		_for(i,1,n){

			if(s[i]=='?'||s[i]=='*'){

				if(i==1)--m;

				a1[m]=GetA1(qwq);

				a2[m]=GetA2(qwq);

				memset(qwq,0,sizeof(qwq));

				op[++m]=(s[i]=='?')?1:2;

			}

			else qwq[++len[m]]=s[i];

		}

		a1[m]=GetA1(qwq);

		a2[m]=GetA2(qwq);

		return;

	}

	inline bool Check(ll a,ll i){

		if(a1[a]!=b.GetHash1(i-len[a]+1,i))return 0;

		if(a2[a]!=b.GetHash2(i-len[a]+1,i))return 0;

		return 1;

	}

	inline void PP(){

		f[0][0]=1;

		_for(i,0,ln)sm[i]=1;

		_for(i,1,m){

			_for(j,0,ln)f[i][j]=0;

			for_(j,ln,len[i]){

				if(Check(i,j)){

					if(op[i]==0)f[i][j]=f[i-1][j-len[i]];

					else if(op[i]==1)f[i][j]=f[i-1][j-len[i]-1];

					else f[i][j]=sm[j-len[i]];

				}

			}

			sm[0]=0;

			_for(j,1,ln)sm[j]=sm[j-1]|f[i][j];

		}

		return;

	}

	inline void In(){

		scanf("%s",s+1);

		n=strlen(s+1),Pre();

		T=rnt();

		while(T--){

			scanf("%s",t+1);

			b.Init(t),ln=strlen(t+1);

			PP(),puts(f[m][ln]?"YES":"NO");

		}

		return;

	}

}

巴特西

「题解报告」 P3167 [CQOI2014]通配符匹配

「题解报告」 P3167 [CQOI2014]通配符匹配

思路

代码

最新文章

热门文章