Submission #7527178

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <string>
#include <iostream>
#include <complex>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <stack>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <random>
#include <set>
#include <vector>
#include <unordered_map>
#include <bitset>
#include <unordered_set>
#include <array>
#include <forward_list>
#include <chrono>
#include <iomanip>
#include <utility>
#include <assert.h>

#pragma GCC optimize("Ofast")
#pragma target("sse", "sse1")

#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());

const ll p1 = 31, m1 = 1e9 + 7, p2 = 29, m2 = 1e9 + 9;
ll p11[100000], p22[100000];

struct Hash
{
	ll h1, h2;
	Hash() {}
	Hash(const ll& _h1, const ll& _h2)
	{
		h1 = _h1;
		h2 = _h2;
	}
	bool operator ==(const Hash& a) const
	{
		return (h1 == a.h1 && h2 == a.h2);
	}
	void operator +=(const Hash& a)
	{
		h1 += a.h1;
		h2 += a.h2;
		if (h1 >= m1)
			h1 -= m1;
		if (h2 >= m2)
			h2 -= m2;
	}
	void operator -=(const Hash& a)
	{
		h1 -= a.h1;
		h2 -= a.h2;
		if (h1 < 0)
			h1 += m1;
		if (h2 < 0)
			h2 += m2;
	}
	void operator *=(const int& x)
	{
		h1 *= p11[x];
		if (h1 >= m1)
			h1 %= m1;
		h2 *= p22[x];
		if (h2 >= m2)
			h2 %= m2;
	}
	Hash operator +(const Hash& a)const
	{
		ll x = h1 + a.h1, y = h2 + a.h2;
		if (x >= m1)
			x -= m1;
		if (y >= m2)
			y -= m2;
		return Hash(x, y);
	}
	Hash operator *(const int& z)const
	{
		ll x = h1 * p11[z], y = h2 * p22[z];
		if (x >= m1)
			x %= m1;
		if (y >= m2)
			y %= m2;
		return Hash(x, y);
	}
	Hash operator -(const Hash& a)const
	{
		ll x = h1 - a.h1, y = h2 - a.h2;
		if (x < 0)
			x += m1;
		if (y < 0)
			y += m2;
		return Hash(x, y);
	}
};

bool operator <(const Hash& a, const Hash& b)
{
	if (a.h1 != b.h1)
		return a.h1 < b.h1;
	return a.h2 < b.h2;
}

int m, n;
string s;
vector <Hash> h;

void calc_hashes(const string& s, vector <Hash>& a)
{
	a[0] = Hash(s[0] - 'a' + 1, s[0] - 'a' + 1);
	for (int i = 1; i < n; i++)
		a[i] = (a[i - 1] * 1) + Hash(s[i] - 'a' + 1, s[i] - 'a' + 1);
}

Hash Hash_otr(int l, int r)
{
	if (l == 0)
		return h[r];
	return h[r] - (h[l - 1] * (r - l + 1));
}

bool check(int l1, int r1, int l2, int r2)
{
	Hash a = Hash_otr(l1, r1), b = Hash_otr(l2, r2);
	return (a == b && r1 - l1 == r2 - l2);
}

bool ch(int len)
{
	multiset <Hash> s;
	for (int i = len; i + len - 1 < n; i++)
		s.insert(Hash_otr(i, i + len - 1));
	for (int i = 0; i + len - 1 < n; i++)
	{
		Hash sos = Hash_otr(i, i + len - 1);
		if (s.find(sos) != s.end())
			return true;
		if (!s.empty())
			s.erase(Hash_otr(len + i, len + i + len - 1));
	}
	return false;
}

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#else
	//freopen("rps2.in", "r", stdin);
	//freopen("rps2.out", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	p11[0] = p22[0] = 1;
	for (int i = 1; i < 100000; i++)
	{
		p11[i] = p1 * p11[i - 1];
		if (p11[i] >= m1)
			p11[i] %= m1;
		p22[i] = p2 * p22[i - 1];
		if (p22[i] >= m2)
			p22[i] %= m2;
	}
	cin >> n >> s;
	h.resize(n);
	calc_hashes(s, h);
	int l = 0, r = n;
	while (r - l > 1)
	{
		int mid = (l + r) / 2;
		if (ch(mid))
			l = mid;
		else
			r = mid;
	}
	cout << l;
	return 0;
}

Submission Info

Judge Result