#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
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:51: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]
51 | for (long long k = 1; k <= s[j].length() - s[i].length() + 1; k++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
82 ms |
860 KB |
Output isn't correct |
| 2 |
Incorrect |
472 ms |
860 KB |
Output isn't correct |
| 3 |
Execution timed out |
1027 ms |
1112 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1043 ms |
1116 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1082 ms |
1112 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1040 ms |
1368 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1060 ms |
1372 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1038 ms |
1368 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1004 ms |
3416 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1086 ms |
3420 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1045 ms |
4700 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1042 ms |
4696 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1055 ms |
5724 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1059 ms |
5720 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1030 ms |
5720 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1049 ms |
5980 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1049 ms |
5976 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1070 ms |
5724 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1036 ms |
5720 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1033 ms |
5724 KB |
Time limit exceeded |
