题目大意
给出一个字符串,其中包含两种通配符 ‘?’和 ‘*’ ,‘?’可以代替一个字符,‘*’可以代替一个字符串(长度可以为0)
然后给出几个字符转,判断能否用给出的字符串表示出来
样例解释
给出字符串:*aca?ctc
判断字符串 :acaacatctc
此时用 * 代替 aba 用 ?代替了t,所以输出YES
解题思路
dp + hash
用hash预处理出字符串的前缀和, 方便判断两端字符是否相同
假设 给出字符串 为str1, 要判断的字符串为 str2
f[i][j]表示 第i个通配符与 要str2的前i个字符 匹配是否可行
当第i个通配符是 * 时特殊判断:
因为 * 可以匹配任意长度的字符串,所以 f[i][j] |=f[i][j-1] (如果匹配到 j-1,那让*再匹配一个,一定可行)
然后枚举str2的每个字符,下标为j,
如果f[i][j]可行,继续判断 给出的字符串 中不是通配符(已经固定)的部分是否能匹配,进行转移
注意
1、因为结尾没有通配符,所以在 str1 结尾加上一个 ‘?’, 在每个str2结尾加上任意一个字符,便于处理结尾部分、
2、如果第i个通配符是 * 应将f[i+1][rb] 赋值为 true,(应为*可以是长度为0的,具体看代码注释)
惊喜
这题与洛谷 P2536 [AHOI2005]病毒检测 基本一样(要统计个数,改了一下数据范围) 一份代码,两道紫题~~~
代码&注释
#include <bits/stdc++.h>
using namespace std;
#define ul unsigned long long
const ul p = 666, N = 100000;
ul sx[N+5], sy[N+5], s[N+5];
int len, lenn, w[12], num, t;
char ch[N+5], cc[N+5];
bool f[12][N+5]; // f[i][j] 表示第i个通配符匹配以j结尾的字符(串)
int main(){
s[0] = 1; for (int i = 1; i <= N; i++) s[i] = s[i-1] * p;
scanf ("%s", ch + 1); len = strlen (ch + 1); ch[++len] = '?'; //在末尾加上一个 ?处理结尾部分
for (int i = 1; i <= len; i++) {
sx[i] = sx[i-1] * p + ch[i]; //预处理出 hash 前缀和
if (ch[i] == '*' or ch[i] == '?') w[++num] = i; //记录通配符的下标
}
scanf ("%d", &t);
while (t--) {
scanf ("%s", cc + 1); lenn= strlen (cc + 1);
cc[++lenn] = '!'; //在末尾加上一个 字符处理结尾部分
for (int i = 1; i <= lenn; i++) sy[i] = sy[i-1] * p + cc[i]; //预处理出 hash 前缀和
memset (f, 0, sizeof (f));
f[0][0] = 1; //初始化
for (int i = 0; i <= num; i++) {
if (ch[w[i]] == '*') for (int j = 1; j <= lenn; j++) f[i][j] |= f[i][j-1]; //是 * 特殊处理
for (int j = 0; j <= lenn; j++) {
if (!f[i][j]) continue;
int la = w[i] + 1, ra = w[i+1] - 1, lb = j + 1, rb = j + w[i+1] - w[i] - 1; //计算出两段的左右端点
if (sx[ra] - sx[la-1] * s[ra-la+1] == sy[rb] - sy[lb-1] * s[rb-lb+1]){ //判断两段是否相同
if (ch[w[i+1]] == '?') f[i+1][rb+1] = 1;
else f[i+1][rb] = 1; //注意:如果是 * ,应将f[i+1][rb]赋值为1而不是f[i+1][rb+1] (*可以匹配长度为0的字符串)
}
}
}
if (f[num][lenn]) puts ("YES");
else puts ("NO");
}
return 0;
}