Submission #1172824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172824		Nomio	Savez (COCI15_savez)	C++20	120 / 120	87 ms	16228 KiB

savez

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int mod = 1e9 + 7;
const int maxn = 2e6 + 1;

int h = 37;
ll p[maxn];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	int mx = 1;
	p[0] = 1;
	for(int i = 1; i < maxn; i++) {
		p[i] = p[i - 1] * h;
		p[i] %= mod;
	}
	map<pair<ll, int>, int> m;
	for(int i = 0; i < n; i++) {
		string s;
		cin >> s;
		int cnt = 0;
		int sz = s.size();
		ll hash1 = 0, hash2 = 0;
		for(int i = 0; i < sz; i++) {
			hash1 += ((int)(s[i] - 'A' + 1) * p[i]) % mod;
			hash1 %= mod;
			hash2 *= h;	
			hash2 %= mod;
			hash2 += ((int)(s[sz - i - 1] - 'A' + 1) * p[0]) % mod;
			hash2 %= mod;
//			cout << hash1 << ' ' << hash2 << '\n';
			if(hash1 == hash2) {
				cnt = max(cnt, m[{hash1, i + 1}]);
			}
		}
//		cout << cnt << '\n';
		m[{hash1, sz}] = cnt + 1;
//		cout << hash1 << ' ' << sz << ' ' << cnt + 1 << '\n';
		mx = max(cnt + 1, mx);
	}
	cout << mx << '\n';
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12