[CQOI2014]通配符匹配

题目描述

几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个是星号(”“')，可以匹配0个及以上的任意字符：另一个是问号(”？“)，可以匹配恰好一个任意字符。现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。

输入格式

第一行是一个由小写字母和上述通配符组成的字符串。第二行包含一个整数n，表示文件个数。接下来n行，每行为一个仅包含小写字母字符串，表示文件名列表。

输出格式

输出n行，每行为”YES“或”NO“，表示对应文件能否被通配符匹配。

样例 #1

样例输入 #1

*aca?ctc
6
acaacatctc
acatctc
aacacatctc
aggggcaacacctc
aggggcaacatctc
aggggcaacctct

样例输出 #1

YES
YES
YES
YES
YES
NO

提示

对于1 00%的数据

·字符串长度不超过1 00000

· 1 <=n<=100

·通配符个数不超过10

蜜汁纯暴力，把我炸的妈妈都不认识，呜呜呜┭┮﹏┭┮

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;

typedef unsigned long long ull;
ull base[5211314], pre1[5211314], pre2[5211314];
ull t, len1, len2;
char got[5211314], temp[5211314], ask[5211314];
ull spe[521][2], spenum;

bool Work(int got_pos, int ask_pos, int spe_pos) {
	//got_pos通配符字符串的位置
	//ask_pos询问字符串的位置
	//spe_pos第几个通配符 
	//记得判断最后一个字符是不是在最后一位 
	//记得判断最后一个通配符 
	int len;
	int gl = got_pos, gr, al, ar;
	ull gans, aans;
	if (got_pos > len1) return false; 
	if (ask_pos > len2) return false;
	//若超出范围 
	if (spe_pos == spenum + 1) {
		gl = got_pos, gr = len1;
		al = ask_pos, ar = len2;
		gans = pre1[gr] - pre1[gl - 1] * base[gr - gl + 1];
		aans = pre2[ar] - pre2[al - 1] * base[ar - al + 1];
		if (gans == aans) return true;
		else return false;
	} 
	if (spe[spe_pos][0] != 0) flag1 = false;
	else flag1 = true;
	if (spe[spe_pos + 1][0] != 0) flag2 = false;
	else flag2 = true; 
	gr = spe[spe_pos + 1][flag2] - 1;
	//gr 为got上对应匹配的右端点 注意判断spe_pos的值是否为spenum 
	len = ((spe[spe_pos + 1][flag2] - 1) - (spe[spe_pos][flag1] + 1)) + 1;
	//len 为两个通配符之间的字符个数
	if (spe_pos == spenum) len = 0;
	//特判最后一个通配符 
	for (int i = ask_pos; i <= len2 - len + 1; ++ i) {
		if (spe_pos == 0) {
			if (len == 0) {
				//如果字符串第一个就是通配符 
				//** 注意 ** 用不用管flag2??? 
				return Work(got_pos + 1, ask_pos, spe_pos + 1))
				//下一个函数的got_pos注意要加一 
			}
			else {
				//将两个字符串比较 
				al = i;
				ar = al + len - 1;//非通配符串的右节点 
				if (ar > len2) return false;
				//如果通配符子串的长度大于非通配符子串的长度 
				gans = pre1[gr] - pre1[gl - 1] * base[gr - gl + 1];
				aans = pre2[ar] - pre2[al - 1] * base[ar - al + 1];
				if (gans == aans) {
					return Work(spe[spe_pos + 1][falg2], ar + 1, spe_pos + 1);
					//这里下一个函数如果不能返回true， 那么一定返回false 
				}
				else return false;//如果不等于则直接返回false 
			}
		}
		else if (spe_pos == spenum){
			if (flag1 == 1) {
				//当最后一个通配符是"*"的时候 
				if (got_pos - 1 == len1) return true;//若最后一个字符是"*" 
				if (Work(got_pos, i, spe_pos + 1)) return true;
				else return false;
				//将got_pos到len1的子串与i到len2的子串比较 
			}
		}
	} 
	return false;
}

int main() {
	base[0] = 1;
	for (int i = 1; i <= 114514; ++ i) {
		base[i] = base[i - 1] * 13331;
	}
	scanf("%s", temp);
	len1 = strlen(temp);
	for (int i = 0; i < len1; ++ i) {
		got[i + 1] = temp[i];
	}
	for (int i = 1; i <= len1; ++ i) {
		pre1[i] = pre1[i - 1] * base[1] + (ull)got[i];
		if (got[i] == '*') {
			spe[++ spenum][0] = i;
		}
		else {
			spe[++ spenum][1] = i;
		}
	}
	cin >> t;
	while (t --) {
		scanf("%s", temp);
		len2 = strlen(temp);
		for (int i = 0; i < len2; ++ i) {
			ask[i + 1] = temp[i];
		}
		for (int i = 1; i <= len2; ++ i) {
			pre2[i] = pre2[i - 1] * base[1] + (ull)ask[i];
		}
		bool flag = Work(1, 1, 0);
	}
}