Submission #116847

#	Time	Username	Problem	Language	Result	Execution time	Memory
116847		ntrung03	Lozinke (COCI17_lozinke)	C++17	100 / 100	410 ms	15188 KiB

lozinke

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 17967929219605081
#define base 31
string s[20002];
int h[20002][12];
int p[12];
signed main() {
	int n;
	cin>>n;
	p[0] = 1;
	for(int i=1;i<12;i++)p[i] = (p[i-1]*base)%mod;
	int res = 0;
	for(int i=0;i<n;i++) cin>>s[i];
	map<pair<int,int>,int> hashes;
	for(int i=0;i<n;i++)
	{
		int l = s[i].size();
		for(int j=0;j<l;j++)
		{
			h[i][j] = (j>0?h[i][j-1]:0);
			h[i][j] = ((h[i][j]*base)%mod+s[i][j]-'a'+1)%mod;
		}
		hashes[{h[i][l-1],l}]+=1;
	}
	for(int k =0;k<n;k++)
	{
		int l = s[k].size();
		set<pair<int,int>> ck;
		for(int i=0;i<l;i++)
		for(int j=i;j<l;j++){
			long long ph = h[k][j]-(i>0?h[k][i-1]*p[j-i+1]:0)%mod;
			pair<int,int> hh = {ph,j-i+1};
			if(ck.count(hh)) continue;
			res+=hashes[hh];
			ck.insert(hh);
		}
	}
	printf("%lld",res-n);
}

• Subtask 1: 100 / 100