#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define debug(x) cerr << "[" << #x << "] = [" << x << "]\n"
template<class T> ostream& operator<< (ostream& out, vector<T> v) {
out << '[';
for (int i = 0; i < v.size(); ++i) {
if (i > 0) {
out << ", ";
}
out << v[i];
}
return out << ']';
}
template<class T> ostream& operator<< (ostream& out, set<T> v) {
return out << vector<T>(v.begin(), v.end());
}
template<class A, unsigned int sz> ostream& operator<< (ostream& out, ar<A, sz> a) {
out << '[';
for (int i = 0; i < sz; ++i) {
if (i > 0) out << ", ";
out << a[i];
}
return out << ']';
}
template<class A, class B> ostream& operator<< (ostream& out, pair<A, B> p) {
return out << '[' << p.first << ", " << p.second << ']';
}
template<class A, class B> ostream& operator<< (ostream& out, map<A, B> mp) {
return out << vector<pair<A, B>>(mp.begin(), mp.end());
}
const int M=1e9+7, B=31;
int n;
ll ans;
map<string, int> oc[11];
map<int, int> mp;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i=0; i<n; ++i) {
string s;
cin >> s;
++oc[s.size()][s];
}
for (int i=1; i<=10; ++i) {
for (auto& x : oc[i]) {
set<int> st;
string s=x.first;
int cnt=x.second;
ans+=(ll)cnt*(cnt-1);
//cout << s << " " << cnt << endl;
//debug(s);
for (int i=0; i<s.size(); ++i) {
ll hsh=0;
for (int j=i; j<s.size(); ++j) {
hsh=(B*hsh+s[j])%M;
st.insert(hsh);
}
}
//debug(mp);
//debug(st);
for (const int& j : st) {
if (mp.count(j)) {
ans+=(ll)cnt*mp[j];
//cout << s << " " << cnt << " " << mp[j] << endl;
}
}
//debug(ans);
ll hsh=0;
for (char c : s)
hsh=(B*hsh+c)%M;
mp[hsh]+=cnt;
}
}
cout << ans;
return 0;
}
Compilation message
lozinke.cpp: In function 'int main()':
lozinke.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for (int i=0; i<s.size(); ++i) {
| ~^~~~~~~~~
lozinke.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (int j=i; j<s.size(); ++j) {
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
312 KB |
Output is correct |
| 5 |
Correct |
5 ms |
332 KB |
Output is correct |
| 6 |
Correct |
7 ms |
460 KB |
Output is correct |
| 7 |
Correct |
9 ms |
516 KB |
Output is correct |
| 8 |
Correct |
8 ms |
460 KB |
Output is correct |
| 9 |
Correct |
37 ms |
972 KB |
Output is correct |
| 10 |
Correct |
34 ms |
1148 KB |
Output is correct |
| 11 |
Correct |
57 ms |
1496 KB |
Output is correct |
| 12 |
Incorrect |
65 ms |
1588 KB |
Output isn't correct |
| 13 |
Correct |
82 ms |
1996 KB |
Output is correct |
| 14 |
Incorrect |
111 ms |
2500 KB |
Output isn't correct |
| 15 |
Correct |
74 ms |
2136 KB |
Output is correct |
| 16 |
Correct |
14 ms |
636 KB |
Output is correct |
| 17 |
Correct |
3 ms |
460 KB |
Output is correct |
| 18 |
Correct |
3 ms |
460 KB |
Output is correct |
| 19 |
Incorrect |
69 ms |
1964 KB |
Output isn't correct |
| 20 |
Correct |
15 ms |
676 KB |
Output is correct |
