个人觉得复杂度是o(n)但是在第三个点t了...莫非是class常数太大了
查看原帖
个人觉得复杂度是o(n)但是在第三个点t了...莫非是class常数太大了
237893
donkeys楼主2021/8/6 07:40
#include<iostream>
#include<cstring>
#define ull unsigned long long
using namespace std;
const int N = 100005, L = 1000006;
const int base1 = 63, base2 = 67, mod1 = 10000017, mod2 = 10000019;
int n;
ull bsl1[L], bsl2[L];
class Hash
{
	ull hash1[L], hash2[L];
	int getnum(char a)
	{
		if (a >= 'a' && a <= 'z')
			return a - 'a' + 1;
		if (a >= 'A' && a <= 'Z')
			return a - 'A' + 27;
		return a - '0' + 53;
	}
public:
	int len;
	void init(char a[])
	{
		memset(hash1, 0, sizeof(hash1)), memset(hash2, 0, sizeof(hash2));
		len = strlen(a + 1);
		for (int i = 1; i <= len; ++i)
		{
			hash1[i] += getnum(a[i]), hash2[i] += getnum(a[i]);
			hash1[i + 1] = hash1[i] * base1, hash2[i + 1] = hash2[i] * base2;
		}
	}
	void add(char a[])
	{
		int nl = len + strlen(a + 1);
		for (int i = len + 1; i <= nl; ++i)
		{
			hash1[i] += getnum(a[i - len]), hash2[i] += getnum(a[i - len]);
			hash1[i + 1] = hash1[i] * base1, hash2[i + 1] = hash2[i] * base2;
		}
		len = nl;
	}
	pair<ull, ull> get(int begin, int end)
	{
		return
		{
			(hash1[end] + mod1 - hash1[begin - 1] * bsl1[end - begin + 1] % mod1) % mod1,
			(hash2[end] + mod2 - hash2[begin - 1] * bsl2[end - begin + 1] % mod2) % mod2
		};
	}
}hashlist, thl;
bool check(Hash& front, Hash& back, int len)
{
	if (front.get(front.len - len + 1, front.len) == back.get(1, len))
		return 1;
	return 0;
}
int search(Hash& front, Hash& back)
{
	for (int i = min(front.len, back.len); i; --i)
	{
		if (check(front, back, i))
			return i;
	}
	return 0;
}
char tmp[L];
int main()
{
	ios::sync_with_stdio(false);
	bsl1[0] = bsl2[0] = 1;
	for (int i = 1; i < L; ++i)
	{
		bsl1[i] = bsl1[i - 1] * base1 % mod1,
			bsl2[i] = bsl2[i - 1] * base2 % mod2;
	}
	cin >> n;
	cin >> tmp + 1;
	cout << tmp + 1;
	hashlist.init(tmp);
	for (int i = 1; i < n; ++i)
	{
		cin >> tmp + 1;
		thl.init(tmp);
		int len = search(hashlist, thl), tmplen = thl.len;
		for (int i = len + 1; i <= tmplen; ++i)
			cout << tmp[i];
		hashlist.add(tmp + len);
	}
	return 0;
}
2021/8/6 07:40
加载中...