#include <bits/stdc++.h>
#define quick ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file(name) freopen(name".inp","r",stdin); freopen(name".out","w",stdout);
#define endl '\n'
#define N 100000
#define pii pair <int,int>
using namespace std;
const int INF = 1e9;
const int base=1001;
const int mod=1e10+7;
const int MOD=1e10+3;
vector <long long> sum[N],SUM[N];
vector <long long> h,H;
int n;
string st[N];
long long get(int u,int v, vector <long long> &s,vector <long long> hh,long long mo)
{
long long mm=mo*mo;
return (s[v]-s[u-1]*h[v-u+1]+mm)%mo;
}
bool cmp(string a,string b)
{
return a.size()<b.size();
}
int main()
{
quick;
//file("pass");
cin>>n;
for (int i=1;i<=n;i++) cin>>st[i];
sort(st+1,st+n+1,cmp);
for (int i=1;i<=n;i++)
{
string s;
s=st[i];
int m=s.size();
s=' '+s;
sum[i].push_back(0);
SUM[i].push_back(0);
for (int j=1;j<=m;j++) sum[i].push_back((sum[i][j-1]*base+s[j])%mod);
for (int j=1;j<=m;j++) SUM[i].push_back((SUM[i][j-1]*base+s[j])%MOD);
}
h.push_back(1);
H.push_back(1);
for (int i=1;i<=100;i++) h.push_back(h[i-1]*base%mod);
for (int i=1;i<=100;i++) H.push_back(H[i-1]*base%mod);
long long ans=0;
for (int i=1;i<n;i++)
{
long long a=get(1,st[i].size(),sum[i],h,mod),b=get(1,st[i].size(),SUM[i],H,MOD);
// cout<<a<<' '<<b<<endl;
for (int j=i+1;j<=n;j++)
for (int k=1;k<=st[j].size()-st[i].size()+1;k++)
{
// cout<<j<<' '<<get(k,k+st[i].size()-1,sum[j],h,mod)<<' '<<get(k,k+st[i].size()-1,SUM[j],H,MOD)<<endl;
if (a==get(k,k+st[i].size()-1,sum[j],h,mod) && b==get(k,k+st[i].size()-1,SUM[j],H,MOD))
{
ans++;
if (st[i]==st[j]) ans++;
break;
}
}
}
cout<<ans;
return 0;
}
Compilation message
lozinke.cpp:10:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.0000000007e+10' to '2147483647' [-Woverflow]
10 | const int mod=1e10+7;
| ~~~~^~
lozinke.cpp:11:19: warning: overflow in conversion from 'double' to 'int' changes value from '1.0000000003e+10' to '2147483647' [-Woverflow]
11 | const int MOD=1e10+3;
| ~~~~^~
lozinke.cpp: In function 'int main()':
lozinke.cpp:53:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for (int k=1;k<=st[j].size()-st[i].size()+1;k++)
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
8284 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8156 KB |
Output is correct |
| 3 |
Correct |
4 ms |
8284 KB |
Output is correct |
| 4 |
Correct |
11 ms |
8336 KB |
Output is correct |
| 5 |
Correct |
48 ms |
8284 KB |
Output is correct |
| 6 |
Correct |
85 ms |
8540 KB |
Output is correct |
| 7 |
Correct |
229 ms |
8540 KB |
Output is correct |
| 8 |
Correct |
130 ms |
8540 KB |
Output is correct |
| 9 |
Execution timed out |
1040 ms |
9816 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1058 ms |
10332 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1055 ms |
10844 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1056 ms |
11868 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1075 ms |
12892 KB |
Time limit exceeded |
| 14 |
Execution timed out |
1042 ms |
11608 KB |
Time limit exceeded |
| 15 |
Execution timed out |
1069 ms |
12636 KB |
Time limit exceeded |
| 16 |
Execution timed out |
1008 ms |
13916 KB |
Time limit exceeded |
| 17 |
Execution timed out |
1070 ms |
13660 KB |
Time limit exceeded |
| 18 |
Execution timed out |
1074 ms |
12892 KB |
Time limit exceeded |
| 19 |
Execution timed out |
1073 ms |
12124 KB |
Time limit exceeded |
| 20 |
Execution timed out |
1062 ms |
12124 KB |
Time limit exceeded |
