#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 || s[i].length() > s[j].length())
{
continue;
}
if (s[i] == s[j] && 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
lozinke.cpp: In function 'int main()':
lozinke.cpp:33:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (long long j = 1; j <= s[i].length() - 1; j++)
| ~~^~~~~~~~~~~~~~~~~~~~
lozinke.cpp:54:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (long long k = 1; k <= s[j].length() - s[i].length() + 1; k++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
856 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
860 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
1116 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
1116 KB |
Output isn't correct |
| 5 |
Incorrect |
16 ms |
1340 KB |
Output isn't correct |
| 6 |
Incorrect |
31 ms |
1372 KB |
Output isn't correct |
| 7 |
Incorrect |
69 ms |
1368 KB |
Output isn't correct |
| 8 |
Incorrect |
50 ms |
1368 KB |
Output isn't correct |
| 9 |
Execution timed out |
1034 ms |
3416 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1020 ms |
3416 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1074 ms |
4700 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1057 ms |
4700 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1058 ms |
5724 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1074 ms |
5724 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1045 ms |
5720 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1082 ms |
5976 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1031 ms |
5976 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1065 ms |
5724 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1028 ms |
5720 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1030 ms |
5720 KB |
Time limit exceeded |
