#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fol(i,a,b) for(int i=a;i>=b;i--)
#define base 31
#define ll long long
#define maxn 1000000
#define f first
#define s second
#define pb push_back
#define el cout << '\n'
#define pii pair<int,int>
const int inf=1e9+7;
const int mod=1e9+7;
using namespace std;
string inp[maxn];
int n;
namespace task1{
int h[10][maxn],p[maxn];
ll get(int i,int l,int r){
return (h[i][r]-h[i][l-1]*p[(r-l+1)]%mod+mod)%mod;
}
void solve(){
p[0]=1;
fo(i,1,11) p[i]=p[i-1]*base%mod;
fo(i,1,n) {
int k=inp[i].size();
string s=' '+inp[i];
fo(j,1,k) h[i][j]=(h[i][j-1]*base+s[j]-'a'+1)%mod;
}
int res=0;
fo(i,1,n){
fo(j,1,n)if(i!=j && inp[i].size()<=inp[j].size()){
fo(k,0,inp[j].size()-inp[i].size()+1) {
//cout <<get(i,1,inp[i].size())<< ' '<<get(j,k+1,k+inp[i].size()),el;
if(get(i,1,inp[i].size())==get(j,k+1,k+inp[i].size())){
res++;
break;
}
}
}
}
cout <<res;
}
}
namespace task2{
int h[10][maxn],p[maxn];
ll get(int i,int l,int r){
return (h[i][r]-h[i][l-1]*p[(r-l+1)]%mod+mod)%mod;
}
void solve(){
p[0]=1;
fo(i,1,11) p[i]=p[i-1]*base%mod;
fo(i,1,n) {
int k=inp[i].size();
string s=' '+inp[i];
fo(j,1,k) h[i][j]=(h[i][j-1]*base+s[j]-'a'+1)%mod;
}
map<int,int > m;
fo(i,1,n){
fo(k,1,inp[i].size()){
string s=' '+inp[i];
map<int,int> ch;
fo(j,1,inp[i].size()-k+1) if(ch[get(i,j,j+k-1)]==0) m[get(i,j,j+k-1)]++,ch[get(i,j,j+k-1)]++;
}
}
int res=0;
fo(i,1,n) res+=m[get(i,1,inp[i].size())]-1;
cout <<res;
}
}
signed main(){
cin >> n;
fo(i,1,n) cin >> inp[i];
if(n<2000) task1::solve();
else task2::solve();
}
Compilation message
lozinke.cpp: In function 'void task1::solve()':
lozinke.cpp:3:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define fo(i,a,b) for(int i=a;i<=b;i++)
......
34 | fo(k,0,inp[j].size()-inp[i].size()+1) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:34:5: note: in expansion of macro 'fo'
34 | fo(k,0,inp[j].size()-inp[i].size()+1) {
| ^~
lozinke.cpp: In function 'void task2::solve()':
lozinke.cpp:3:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define fo(i,a,b) for(int i=a;i<=b;i++)
......
61 | fo(k,1,inp[i].size()){
| ~~~~~~~~~~~~~~~~~
lozinke.cpp:61:4: note: in expansion of macro 'fo'
61 | fo(k,1,inp[i].size()){
| ^~
lozinke.cpp:3:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define fo(i,a,b) for(int i=a;i<=b;i++)
......
64 | fo(j,1,inp[i].size()-k+1) if(ch[get(i,j,j+k-1)]==0) m[get(i,j,j+k-1)]++,ch[get(i,j,j+k-1)]++;
| ~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:64:5: note: in expansion of macro 'fo'
64 | fo(j,1,inp[i].size()-k+1) if(ch[get(i,j,j+k-1)]==0) m[get(i,j,j+k-1)]++,ch[get(i,j,j+k-1)]++;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
64148 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
41 ms |
64092 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
38 ms |
64092 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
36 ms |
64092 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
38 ms |
64080 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
39 ms |
63976 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
38 ms |
64304 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
51 ms |
64080 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
43 ms |
64336 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
38 ms |
64332 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
39 ms |
64372 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
57 ms |
64420 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
44 ms |
64336 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
41 ms |
64336 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
52 ms |
64308 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
55 ms |
64340 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
43 ms |
64436 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
43 ms |
64340 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
41 ms |
64344 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
42 ms |
64276 KB |
Execution killed with signal 11 |
