这样：
```
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
namespace my {
typedef unsigned long long ull;
const int maxn(112345);
const ull base(23);//选择的进制数
ull power[maxn];//power[i] = base ^ i，其中'^'表示幂
inline void init_power() {
power[0] = 1;
for (int i(1); i != maxn; ++i) {
power[i] = power[i - 1] * base;
}
}
class string {//自己写的string，封装了一下hash相关的函数
public:
string() : end(0) {}
char& operator[](int p) {
return str[p];
}
void clear() { end = 0; }
void read() {//读入
end = 0;
char c(getchar());
while (c < 'a' || c > 'z') c = getchar();
str[end++] = 'a';//在字符串收尾统一加入相同字符不会影响答案，且避免了结尾、开头是通配符的情况。
do {
str[end++] = c;
c = getchar();
} while (c >= 'a' && c <= 'z');
str[end++] = 'a';
init_hash();
}
bool empty() const { return end == 0; }
int size() const { return end; }
void push_back(char c) {//向该string中加入字符
if (c == '?') pos.push_back(end);//pos记录了该string所有'?'的位置（原因是我在分段时只调用这个函数向string中加入字符）
str[end++] = c;
}
void init_hash() {//初始化hash，原理如上所述
hash[end] = 0;
for (int i(end - 1); i >= 0; --i) {
hash[i] = hash[i + 1] * base + str[i];
}
}
ull gethash(int beg, int len) const {//获得其中某一段的hash值
return hash[beg] - hash[beg + len] * power[len];
}
ull gethash() const {//获得整段的hash值，程序中似乎没有用到
return hash[0];
}
std::vector<int> pos;//pos记录所有'?'的位置
protected:
char str[maxn];
ull hash[maxn];
int end;
}seg[20], head, tail, dest;//四者分别是：模板串分出来的每一段，模板串的首，模板串的尾，目标串（询问串）
char str[maxn];
int endseg, lenstr;//endseg即分出来的段数
void init_seg(int len) {//把模板串分段
int left(0), right(len - 1);
while (left <= right) {//先处理首
if (str[left] == '*') break;
head.push_back(str[left++]);
}
head.init_hash();
int pos(right);
while (left <= pos) {//由于尾串大小不定，先找到起始点
if (str[pos] == '*') break;
--pos;
}
for (int i(pos + 1); i <= right; ++i) {
tail.push_back(str[i]);
}
tail.init_hash();
++left; right = pos;
while (left <= right) {//处理出所有的段
if (str[left] == '*') {//每段间的分隔符
if (!seg[endseg].empty())//为避免ab******c的情况，判断一下是否为空
seg[endseg].init_hash(), ++endseg;//非空，初始化hash值
++left;
continue;
} else {
seg[endseg].push_back(str[left++]);//加入段中
}
}
if (!seg[endseg].empty()) ++endseg;//如果endseg中有元素，++endseg使其指向超出末端下一位
}
inline bool match(int s, int beg) {//常识将段seg[s]与目标串beg处开始的字符串进行匹配
int front(0);
for (int i(0); i != seg[s].pos.size(); ++i) {//枚举'?'间的字符串
int len(seg[s].pos[i] - front);
if (seg[s].gethash(front, len) != dest.gethash(beg, len)) {//hash值不相等，一定没对上
return false;
}
beg += len + 1;
front += len + 1;//匹配上了，那么继续匹配下一个。+1是表示这里跳了一个字符(即'?')
}
int len(seg[s].size() - front);
if (seg[s].gethash(front, len) != dest.gethash(beg, len)) return false;//最后没有'?'之后可能还有一段需要比较
return true;
}
inline bool com_seg(int s, int& left, int right) {
while (left <= right) {//尝试将段seg[s]与dest在[left, right]间的子串进行匹配
if (match(s, left)) {
left += seg[s].size();//如果成功匹配，left就往后跳到下一个需要匹配的起始位置
return true;
}
++left;//匹配失败，尝试++left继续匹配
}
return false;
}
inline bool cmpstr(string& a, int x, string& b, int y, int len) {//比较a从x处的长度为len的字符串是否与b从y处开始的长度为len的字符串相等
for (int i(0); i != len; ++i) {
if (a[x + i] != b[y + i] && a[x + i] != '?' && b[y + i] != '?') return false;
}
return true;
}
void compare() {//整体的匹配
int left(0), right(dest.size() - 1);
if (head.size() > dest.size() || tail.size() > dest.size()) {//首、尾串大小对不上，一定错了。
printf("NO\n");
return;
}
if (!cmpstr(head, 0, dest, 0, head.size())) {//由于插入了'a'，模板串的首串一定不是通配符，一定要与目标串的开头匹配。
printf("NO\n");
return;
} else {
left = head.size();
}
if (!cmpstr(tail, 0, dest, right - tail.size() + 1, tail.size())) {//与上同理，匹配尾串
printf("NO\n");
return;
}
else {
right = right - tail.size();
}
for (int i(0); i != endseg; ++i) {
if (!com_seg(i, left, right)) {尝试将段seg[i]与left到right的字符串匹配（可以跳跃，因为段的收尾都是被抹去的'\*'）
printf("NO\n");
return;
}
}
printf("YES\n");
}
int main() {
init_power();//一些初始化和函数调用
int T;
scanf("%s%d", str + 1, &T);
str[0] = 'a';
str[lenstr = ::strlen(str)] = 'a';
init_seg(++lenstr);
while (T--) {
dest.read();
compare();
}
return 0;
}
}
int main() {
return my::main();
}
```
by 陈启旺 @ 2019-04-10 19:29:58
可能是下标越界，访问负下标
by _•́へ•́╬_ @ 2022-08-17 19:02:11