【HNOI2014】抄卡组

题面

题解

如果所有的字符串都有通配符，那么只要比较不含通配符的前缀和后缀就可以了。

否则一定有一个串没有通配符。找出这个字符串，然后将所有串与这个串匹配，通配符将(B)分成一段一段在(A)上匹配，然后越早出现越好，这里用(mathrm{KMP, hash})都可以

讲起来容易，但是写起来的话就有点复杂了

时间复杂度：(mathrm{O}(sum mid S_imid))

代码复杂度：(mathrm{O}(infty))

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#include<string>
#define RG register

const unsigned long long X(60923);
unsigned long long val[10000010];
const int maxn(100010);
std::string s[maxn], s1[maxn];
std::vector<unsigned long long> h[maxn];
std::vector<int> pos[maxn];
inline int cmp(const std::string &lhs, const std::string &rhs)
	{ return lhs.length() < rhs.length(); }
int T, n;

void calc(int i)
{
	pos[i].clear(), h[i].clear();
	pos[i].push_back(-1), h[i].push_back(0);
	for(std::string::iterator it = s[i].begin(); it != s[i].end(); ++it)
	{
		h[i].push_back(h[i].back() * X + *it);
		if(*it == '*') pos[i].push_back(it - s[i].begin());
	}
	pos[i].push_back(s[i].length());
}

inline unsigned long long Hash(const std::vector<unsigned long long> &vec,
		int l, int r)
{
	++l, ++r;
	return vec[r] - vec[l - 1] * val[r - l + 1];
}

bool check(int x, int y)
{
	int lenx = s[x].length(), leny = s[y].length();
	if(s[y].find('*') != std::string::npos)
		std::swap(x, y), std::swap(lenx, leny);
	if(s[x].find('*') == std::string::npos
			&& s[y].find('*') == std::string::npos)
		return Hash(h[x], 0, s[x].length() - 1) == Hash(h[y], 0, s[y].length() - 1);
	else
	{
		std::string A = ""; std::string::size_type p = 0;
		for(RG int i = 1; i < pos[x].size(); i++)
		{
			int tpos = p, len = pos[x][i] - pos[x][i - 1] - 1;
			while(tpos + len - 1 < s[y].length() &&
					Hash(h[x], pos[x][i - 1] + 1, pos[x][i] - 1)
				!= Hash(h[y], tpos, tpos + len - 1)) ++tpos;
			if(tpos + len - 1 >= s[y].length()) return false;
			if(tpos != 0 && p == 0) return false;
			p = tpos + len;
		}
		return true;
	}
}

void Doit()
{
	int pos = -1;
	for(RG int i = 1; i <= n; i++) calc(i);
	for(RG int i = 1; i <= n; i++)
		if(s[i].find('*') == std::string::npos) { pos = i; break; }
	if(pos == -1)
	{
		for(RG int i = 1; i <= n; i++)
		{
			s1[i] = "";
			for(RG int j = 0; j < s[i].length(); j++)
				if(s[i][j] == '*') break;
				else s1[i] += s[i][j];
		}
		std::sort(s1 + 1, s1 + n + 1, cmp);
		for(RG int i = 2; i <= n; i++)
		{
			for(RG int j = 0; j < s1[i - 1].length(); j++)
				if(s1[i][j] != s1[i - 1][j])
					return (void)(std::cout << 'N' << std::endl);
		}
		
		for(RG int i = 1; i <= n; i++)
		{
			s1[i] = "";
			for(RG int j = s[i].length() - 1; ~j; j--)
				if(s[i][j] == '*') break;
				else s1[i] += s[i][j];
		}
		std::sort(s1 + 1, s1 + n + 1, cmp);
		for(RG int i = 2; i <= n; i++)
		{
			for(RG int j = 0; j < s1[i - 1].length(); j++)
				if(s1[i][j] != s1[i - 1][j])
					return (void)(std::cout << 'N' << std::endl);
		}
	}
	else for(RG int i = 1; i <= n; i++)
	{
		if(i == pos) continue;
		// std::cout << i << std::endl;
		if(!check(i, pos)) return (void)(std::cout << 'N' << std::endl);
	}
	std::cout << 'Y' << std::endl;
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin >> T, val[0] = 1;
	for(RG int i = 1; i <= 10000000; i++) val[i] = val[i - 1] * X;
	while(T--)
	{
		std::cin >> n;
		for(RG int i = 1; i <= n; i++)
			std::cin >> s[i];
		Doit();
	}
	return 0;
}