#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[maxn][11],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];
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 |
Incorrect |
15 ms |
31576 KB |
Output isn't correct |
| 2 |
Correct |
15 ms |
31580 KB |
Output is correct |
| 3 |
Incorrect |
15 ms |
31792 KB |
Output isn't correct |
| 4 |
Correct |
14 ms |
31576 KB |
Output is correct |
| 5 |
Incorrect |
17 ms |
32092 KB |
Output isn't correct |
| 6 |
Incorrect |
20 ms |
32092 KB |
Output isn't correct |
| 7 |
Incorrect |
22 ms |
32588 KB |
Output isn't correct |
| 8 |
Correct |
27 ms |
32860 KB |
Output is correct |
| 9 |
Incorrect |
46 ms |
33692 KB |
Output isn't correct |
| 10 |
Incorrect |
86 ms |
36704 KB |
Output isn't correct |
| 11 |
Incorrect |
68 ms |
35152 KB |
Output isn't correct |
| 12 |
Correct |
180 ms |
42580 KB |
Output is correct |
| 13 |
Incorrect |
105 ms |
35412 KB |
Output isn't correct |
| 14 |
Incorrect |
138 ms |
41512 KB |
Output isn't correct |
| 15 |
Incorrect |
197 ms |
42580 KB |
Output isn't correct |
| 16 |
Incorrect |
95 ms |
33108 KB |
Output isn't correct |
| 17 |
Correct |
40 ms |
32604 KB |
Output is correct |
| 18 |
Correct |
30 ms |
32604 KB |
Output is correct |
| 19 |
Incorrect |
127 ms |
37784 KB |
Output isn't correct |
| 20 |
Incorrect |
56 ms |
32860 KB |
Output isn't correct |
