HDU 5510 Bazinga

Posted on By 二价氢

试题:HDU 5510

给定500个字符串\(S_1..S_{500}\),求最大的\(i\),使得\(\exists j \in [1, i], S_j\)不为\(S_i\)的子串

一个感觉不靠谱的算法:

对于第\(i\)个字符串,如果字符串\(j\)是它的子串,那么对于第\(i+1\)个字符串,我们不必统计字符串\(S_j\),确定字符串的包含关系可用KMP算法实现

最差复杂度:\(O(n^2L)\)

实际情况下很快

事实上,可用string.find()来实现,虽然效率更低

暴力出奇迹!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
char s[500 + 1][2000 + 1];
int nxt[500 + 1][2000 + 1];
int n, t;
vector<int> v, tmp;
void kmp_prep(int k)
{
	int *next = nxt[k];
	char *str = s[k];
	int len = strlen(str);
	for (int i = 1; i < len; i++)
	{
		int j = i;
		while (j > 0)
		{
			j = next[j];
			if (str[j] == str[i])
			{
				next[i + 1] = j + 1;
				break;
			}
		}
	}
}
bool kmp_doit(int x, int y) // find *y* in *x*
{
	char *xx = s[x];
	char *yy = s[y];
	int lenx = strlen(xx);
	int leny = strlen(yy);
	int *next = nxt[y];
	for (int i = 0, j = 0; i < lenx; i++)
	{
		if (j < leny && xx[i] == yy[j])
			j++;
		else
			while (j > 0)
			{
				j = next[j];
				if (xx[i] == yy[j])
				{
					j++;
					break;
				}
			}
		if (j == leny)
			return true;
	}
	return false;
}
bool check_it(int x)
{
	bool ret = false;
	tmp.clear();
	for (int i = 0; i < v.size(); i++)
	{
		if (!kmp_doit(x, v[i]))
		{
			tmp.push_back(v[i]);
			ret = true;
		}
	}
	tmp.push_back(x);
	v = tmp;
	return ret;
}
int work()
{
	memset(s, 0, sizeof(s));
	memset(nxt, 0, sizeof(nxt));
	scanf("%d", &n);
	int ans = -1;
	v.clear();
	for (int i = 0; i < n; i++)
	{
		scanf("%s", s[i]);
		kmp_prep(i);
		if (check_it(i))
			ans = i + 1;
	}
	return ans;
}
int main()
{
	int t;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++)
	{
		printf("Case #%d: %d\n", i, work());
	}
	return 0;
}