# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1078719 | khactrung1912 | Lozinke (COCI17_lozinke) | C++14 | 4 ms | 3160 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define el "\n"
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define inpout(x) freopen(x".inp", "r", stdin), freopen(x".out", "w", stdout)
const int maxn = 2e4 + 5;
const ll mod = 1e9 + 7;
const ll base = 31;
const ll Mod[4] = {(ll)1e9 + 1677, (ll)1e9 + 2277, (ll)1e9 + 3577, (ll)1e9 + 3777};
int n, i, ans;
string s[maxn];
vector<ll> Hash[4][maxn];
ll pw[4][maxn];
bool check(int u, int v){
if (s[u].size() < s[v].size())
return false;
for (int j = 1; j <= s[u].size() - s[v].size() + 1; j++){
bool ok = true;
int l = j, r = j + s[v].size() - 2;
for (int k = 0; k < 4; k++)
if (Hash[k][v][s[v].size() - 1] != (Hash[k][u][r] - Hash[k][u][l - 1] * pw[k][r - l + 1] + Mod[k] * Mod[k]) % Mod[k])
ok = false;
if (ok)
return true;
}
return false;
}
signed main(){
ios;
inpout("pass");
cin >> n;
for (int k = 0; k < 4; k++){
pw[k][0] = 1;
for (i = 1; i <= 10; i++)
pw[k][i] = pw[k][i - 1] * base;
}
for (i = 1; i <= n; i++){
cin >> s[i];
s[i] = " " + s[i];
for (int k = 0; k < 4; k++)
Hash[k][i].resize(s[i].size());
for (int j = 1; j < s[i].size(); j++)
for (int k = 0; k < 4; k++)
Hash[k][i][j] = (Hash[k][i][j - 1] * base + s[i][j] - 'a') % Mod[k];
}
for (i = 1; i <= n; i++){
for (int j = 1; j <= n; j++)
if (i != j && check(i, j))
ans++;
}
cout << ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |