Submission #44282

#	Time	Username	Problem	Language	Result	Execution time	Memory
44282		JustInCase	Lozinke (COCI17_lozinke)	C++17	90 / 100	526 ms	11580 KiB

lozinke

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int MAX_N = 2e4 + 5;
const int MAX_S = 15;

//---------------------------------

struct Hash {
	static const int BASE = 131;
	static const int MOD = 1e9 + 7;
	static int basePowers[];

	int h[MAX_S];

	Hash(const string &s);
	void ComputeHash(const string &s);
	static void ComputeBasePowers();
	int CalculateModularInverse(int a, int mod);
	int GetSubstringHash(int low, int high);
};

int Hash::basePowers[MAX_S];

Hash::Hash(const string &s = "") {
	if(s.size() != 0) {
		ComputeHash(s);
	}
}

void Hash::ComputeHash(const string &s) {
	h[0] = 0;

	for(int i = 1; i <= s.size(); i++) {
		h[i] = (1ll * h[i - 1] + 1ll * (s[i - 1] - 'a' + 1) * basePowers[i]) % MOD;
	}
}

void Hash::ComputeBasePowers() {
	basePowers[0] = 1;

	for(int i = 1; i < MAX_S; i++) {
		basePowers[i] = (1ll * basePowers[i - 1] * BASE) % MOD;
	}
}

int Hash::CalculateModularInverse(int a, int mod) {
	if(mod == 0) {
		return 1;
	}
	
	if(mod % 2 == 0) {
		int p = CalculateModularInverse(a, mod / 2);
		return (1ll * p * p) % MOD;
	}
	else {
		return (1ll * CalculateModularInverse(a, mod - 1) * a) % MOD;
	}
}

int Hash::GetSubstringHash(int low, int high) {
	int substringHash = (1ll * (h[high] - h[low - 1]) * CalculateModularInverse(basePowers[low - 1], MOD - 2)) % MOD;
	if(substringHash < 0) {
		substringHash += MOD;
	}

	return substringHash;
}

//---------------------------------

string s[MAX_N];
Hash hs[MAX_N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	Hash::ComputeBasePowers();

	int n;
	cin >> n;
	
	unordered_map< int, int > cnt;
	for(int i = 0; i < n; i++) {
		cin >> s[i];

		hs[i] = Hash(s[i]);
		cnt[hs[i].h[s[i].size()]]++;
	}

	int ans = 0;
	for(int i = 0; i < n; i++) {
		unordered_map< int, bool > alreadyChecked;
		for(int low = 1; low <= s[i].size(); low++) {
			for(int high = low; high <= s[i].size(); high++) {
				int currSubstringHash = hs[i].GetSubstringHash(low, high);

				if(alreadyChecked.count(currSubstringHash) == 0) {
					ans += cnt[currSubstringHash]; 
					if(low == 1 && high == s[i].size()) {
						ans--;
					}
					
					alreadyChecked[currSubstringHash] = true;
				}
			}
		}
	}

	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

lozinke.cpp: In member function 'void Hash::ComputeHash(const string&)':
lozinke.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i <= s.size(); i++) {
                 ~~^~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:97:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int low = 1; low <= s[i].size(); low++) {
                    ~~~~^~~~~~~~~~~~~~
lozinke.cpp:98:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int high = low; high <= s[i].size(); high++) {
                        ~~~~~^~~~~~~~~~~~~~
lozinke.cpp:103:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(low == 1 && high == s[i].size()) {
                     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 90 / 100