#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int , int>
#define fi first
#define se second
#define endl '\n'
const int INF = (int)1e9;
const int maxn = 20000 + 6;
const int mod = 1e9 + 7;
int n;
string a[maxn];
const int base = 311;
const int nmod = 2;
const int ModHash[4] = {(int)1e9 + 2277 , (int)1e9 + 5277 , (int)1e9 + 8277 , (int)1e9 + 9277};
ll pw[maxn][nmod];
void prepare(int n)
{
for (int i = 0 ; i < nmod ; ++i) pw[0][i] = 1;
for (int i = 1 ; i <= n ; ++i)
for (int j = 0 ; j < nmod ; ++j) pw[i][j] = pw[i - 1][j] * base % ModHash[j];
}
struct HASH{
vector<vector<ll>> HashVal;
void BuildHash(string s)
{
int n = s.size();
HashVal.resize(n + 1);
for (int i = 0 ; i <= n ; ++i) HashVal[i].resize(nmod);
for (int i = 1 ; i <= n ; ++i)
for (int j = 0 ; j < nmod ; ++j)
HashVal[i][j] =( HashVal[i - 1][j] * base + (int)s[i - 1]) % ModHash[j];
}
ll get(int l , int r , int pos)
{
return (HashVal[r][pos] - HashVal[l - 1][pos] * pw[r - l + 1][pos] % ModHash[pos] + ModHash[pos]) % ModHash[pos];
}
} h[maxn];
map<pii , int> m;
ll ans = 0;
void calc(int id)
{
int n = a[id].size();
map<pii , bool> mark;
for (int i = 1 ; i <= n ; ++i)
for (int j = i ; j <= n ; ++j)
{
if ( mark[{ h[id].get(i , j , 0) , h[id].get(i , j , 1)}] == 0)
{
ans += m[{ h[id].get(i , j , 0) , h[id].get(i , j , 1)}];
mark[{ h[id].get(i , j , 0) , h[id].get(i , j , 1)}] = 1;
}
// if (m[{ h[id].get(i , j , 0) , h[id].get(i , j , 1)}])
// cout << id << " " << i << " " << j << " " << ans << endl;
}
m[{ h[id].get(1 , n , 0) , h[id].get(1 , n , 1) } ]++;
// cerr << id << " " << m[{ h[3].get(1 , 1 , 0) , h[3].get(1 , 1 , 1) } ] << " " << m[{ h[1].get(1 , 1 , 0) , h[1].get(1 , 1 , 1) } ]<< endl;
// cerr << a[3][0] << " " << a[1][0] << endl;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
freopen("PASS.INP" , "r" , stdin);
freopen("PASS.OUT" , "w" , stdout);
prepare(15);
cin >> n ;
for (int i = 1 ; i <= n ; ++i) cin >> a[i];
sort(a + 1 , a + n + 1 , [&](string a , string b)
{
return (a.size() != b.size() ? a.size() < b.size() : a < b);
});
// for (int i = 1 ; i <= n ; ++i) cout << a[i] << endl;
for (int i = 1 ; i <= n ; ++i) h[i].BuildHash(a[i]);
for (int i = 1 ; i <= n ; ++i) calc(i);
for (int i = 1 ; i <= n ; ++i)
{
int cnt = m[{ h[i].get(1 , a[i].size() , 0) , h[i].get(1 , a[i].size() , 1) } ];
ans += (cnt - 1);
m[{ h[i].get(1 , a[i].size() , 0) , h[i].get(1 , a[i].size() , 1) } ]--;
}
cout << ans << endl;
return 0;
}
Compilation message
lozinke.cpp: In function 'int main()':
lozinke.cpp:95:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen("PASS.INP" , "r" , stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | freopen("PASS.OUT" , "w" , stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1624 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
1372 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 6 |
Incorrect |
4 ms |
1628 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 8 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
1628 KB |
Output isn't correct |
| 10 |
Incorrect |
3 ms |
1628 KB |
Output isn't correct |
| 11 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 12 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 13 |
Incorrect |
2 ms |
1624 KB |
Output isn't correct |
| 14 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 15 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 16 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 17 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 18 |
Incorrect |
2 ms |
1628 KB |
Output isn't correct |
| 19 |
Incorrect |
2 ms |
1624 KB |
Output isn't correct |
| 20 |
Incorrect |
4 ms |
1628 KB |
Output isn't correct |
