# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1078659 | mamama | Lozinke (COCI17_lozinke) | C++14 | 1086 ms | 5980 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;
const long long mod1 = 1000000007;
const long long mod2 = 79462751;
long long n, powa[15], powb[15], res;
pair<long long, long long> caidautien;
pair<long long, long long> luugiu, chimotdemnuathoi;
pair<long long, long long> hasha[20005][15];
string s[20005];
pair<long long, long long> hashh(long long l, long long r, long long k)
{
caidautien.first = ((hasha[k][r].first - hasha[k][l - 1].first * powa[r - l + 1] + mod1*mod1) % mod1);
caidautien.second = ((hasha[k][r].second - hasha[k][l - 1].second * powb[r - l + 1] + mod2*mod2) % mod2);
return caidautien;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie();
cout.tie();
cin >> n;
powa[0] = 1;
powb[0] = 1;
for (long long i = 1; i <= 12; i++)
{
powa[i] = powa[i - 1]*30 % mod1;
powb[i] = powb[i - 1]*28 % mod2;
}
for (long long i = 1; i <= n; i++)
{
cin >> s[i];
s[i] = "!" + s[i];
for (long long j = 1; j <= s[i].length() - 1; j++)
{
hasha[i][j].first = (hasha[i][j - 1].first*30 + (s[i][j] - 'a' + 1)) % mod1;
hasha[i][j].second = (hasha[i][j - 1].second*28 + (s[i][j] - 'a' + 1)) % mod2;
}
}
res = 0;
for (long long i = 1; i <= n; i++)
{
luugiu = hashh(1, s[i].length() - 1, i);
for (long long j = 1; j <= n; j++)
{
// cout << "\n" << i << " " << j << "\n";
if (i == j)
{
continue;
}
for (long long k = 1; k <= s[j].length() - s[i].length() + 1; k++)
{
// cout << k << " " << k + s[i].length() - 2 << " - ";
chimotdemnuathoi = hashh(k, k + s[i].length() - 2, j);
if (chimotdemnuathoi.first == luugiu.first && chimotdemnuathoi.second == luugiu.second)
{
res++;
// cout << "ok\n";
break;
}
}
}
}
cout << res;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |