通配符 '*' 可以匹配任意个字符 (包含0个). 给出 n 个字符串, 问是否能两两匹配. (n ≤ 10^5, 数据组数 T = 10, 输入文件不超过 10M, n * 最长字符串 ≤ 2*10^8) 注意, 是两两之间匹配, 而非所有字符串匹配.
两个含多个通配符的字符串的匹配让我感觉好晕......@_@
看了题解, 发现只需要关注第一个通配符和最后一个通配符.
先考虑怎样判定两个字符串 s,t 是否匹配. - 均不含通配符. 直接比较. - s 含通配符, t 不含通配符. 设 s 被通配符分割成 s1, s2, ..., sk. 充要条件是 si (1 ≤ i ≤ k) 依次在 t 中出现且不能相互覆盖. - s,t 均含通配符. 对于含有通配符的字符串 x, 记 first(x) 为第一个通配符的位置离开头的距离, last(x) 为最后一个通配符离结尾的距离. 设 a = min(first(s), first(t)), b = min(last(s), last(t)), 充要条件是 prefix(s, a) = prefix(t, a) 且 suffix(s, b) = suffix(t, b). 分类讨论一下, 发现中间的部分总是可以构造一种匹配方式.
怎么样才能自己想到这些呢? 也许从一个通配符的串开始手玩一下吧......
回到原问题. 设不含通配符的字符串构成集合 A, 含通配符的字符串构成集合 B. 1. A. 直接比较. 2. AB. A 中元素相同才进行这一步. 借助 KMP 或字符串哈希, 贪心地匹配即可. 3. B. 借助相等关系的传递性. 按 first 排序, 比较 prefix(B[i], first(B[i])), prefix(B[i+1], first(B[i])). last 同理.
B 内部的判定, 我开始想的是将 B[i] 和 B[i] 后面的串比较, 略过之前已经比较过的部分. 利用传递性, 编码难度降低不少. 不过这样就可以完全不用哈希了......
输入可能有空行, 表示空串. 用 cin 读入一个整数后要 cin.get() 一下, 把缓冲区里的换行符拿掉.
理论上 AC 和实际上 AC 还是有区别的. 除了空行的问题, 还犯了这样几个比较逗的错误: 1. 交换两个对象, 由于没开结构体, 漏掉了一些属性 QAQ 2. 数组太大, CE 了好几发......g++: Internal error: File size limit exceeded (program as) 3. 取子串的哈希值写错 4. 没把数据读完就 return false, 由于本题多组数据, 所以就 GG 了......
typedef unsigned long long ull;
const int N = 1e5 + 1, L = 5e6;
int o[N];
ull H[L] = {1, 131};
string s[N];
vector<ull> h[N];
string::size_type first[N], last[N];
void calc(const string& s, vector<ull>& h)
{
static const char k = '*' - 1;
h.resize(s.size());
ull t = 0;
per (i, s.size()-1, 0) t = h[i] = t * H[1] + s[i] - k;
}
inline ull Hash(const vector<ull>& h, int l, int r)
{
return h[l] - (r == (int)h.size() ? 0 : h[r] * H[r-l]);
}
bool judge(const vector<ull>& u, const string& s, const vector<ull>& v)
{
for (int i = 0, j = 0, k = 0, n = u.size(), m = s.size(); i < n && k < m; j = ++k)
{
while (k < m && s[k] != '*') ++k;
ull t = Hash(v, j, k);
while (i <= n-(k-j) && Hash(u, i, i+k-j) != t) ++i;
if (i > n-(k-j)) return false;
i += k-j;
}
return true;
}
bool by_first(int i, int j)
{
return first[i] < first[j];
}
bool by_last(int i, int j)
{
return last[i] < last[j];
}
bool work()
{
int n, m = 0, x = -1;
cin >> n;
cin.get();
rep (i, 0, n)
{
getline(cin, s[m]);
first[m] = s[m].find_first_of('*');
if (first[m] == string::npos)
{
if (x == -1)
{
x = m++;
}
else if (s[m] != s[x])
{
while (++i < n) getline(cin, s[m]);
return false;
}
}
else
{
last[m] = s[m].size() - s[m].find_last_of('*');
++m;
}
}
if (x != -1)
{
swap(s[x], s[0]);
first[x] = first[0];
last[x] = last[0];
}
else
{
s[m] = s[0];
first[m] = first[0];
last[m] = last[0];
s[0].clear();
++m;
}
rep (i, 0, m) calc(s[i], h[i]);
if (x != -1)
rep (i, 1, m)
if (!judge(h[0], s[i], h[i])) return false;
rep (i, 1, m) o[i] = i;
sort(o+1, o+m, by_first);
rep (j, 1, m-1)
{
int i = o[j];
if (Hash(h[i], 0, first[i]) != Hash(h[o[j+1]], 0, first[i])) return false;
}
rep (i, 1, m) o[i] = i;
sort(o+1, o+m, by_last);
rep (j, 1, m-1)
{
int w = last[o[j]];
if (w > 1 && h[o[j]][h[o[j]].size()-w+1] != h[o[j+1]][h[o[j+1]].size()-w+1]) return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
rep (i, 2, L) H[i] = H[i-1] * H[1];
int T;
cin >> T;
cin.get();
while (T--)
cout << (work() ? 'Y' : 'N') << endl;
return 0;
}