#include<bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 7 ;
int n ;
int dp[N] ;
int ans ;
string ss[N] ;
struct hashing {
long long base ;
long long mod1;
vector<long long> pref;
vector<long long> base_power;
long long normalize(long long x ){
return ((x%mod1) + mod1) %mod1 ;
}
void init(string &str_,long long mod1_ = 1e9 +7, long long base_ = 313){
int sz = str_.size() ;
pref.resize(sz) ;
base_power.resize(sz) ;
base = base_ ;
mod1 = mod1_ ;
base_power[0] = 1 ;
for(int i = 1 ;i <sz ; i++){
base_power[i] = (1ll*base*base_power[i-1]) %mod1 ;
}
long long cur = 0 ;
for(int i = 0 ; i <sz ; i++){
cur = (cur*base + str_[i])%mod1;
pref[i] = cur ;
}
}
long long get(int l , int r){
long long ret = pref[r] ;
if(l){
long long power_difference = base_power[r-l+1];
long long prefix_hash =pref[l-1];
prefix_hash = (prefix_hash*power_difference)%mod1 ;
ret = normalize(ret - prefix_hash) ;
}
return ret ;
}
} shs[N] ;
bool match(int i , int j){
if( abs( (int) ss[i].size() - (int) ss[j].size()) > 1 ) return 0 ;
if(shs[i].get(0 , ss[i].size() ) == shs[j].get(0 , ss[j].size())) return 1 ;
return shs[i].get(0 , ss[i].size() - 1) == shs[j].get(0 , ss[j].size() -1 ) ;
}
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
//freopen("in.in" , "r" , stdin) ;
cin>>n ;
for(int i = 0 ; i < n ;i++){
cin>>ss[i] ;
reverse( ss[i] .begin() , ss[i].end()) ;
shs[i].init(ss[i]) ;
}
sort(ss , ss + n) ;
for(int i = 0 ;i < n ;i++){
dp[i] = 1 ;
for(int j = 0 ; j < i ; j++){
if(match(j , i)){
dp[i] = max(dp[i] , dp[j]+1) ;
}
}
ans = max(ans , dp[i]) ;
}
cout<< ans ;
return 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9728 KB |
Output isn't correct |
| 2 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 3 |
Incorrect |
10 ms |
9728 KB |
Output isn't correct |
| 4 |
Runtime error |
51 ms |
37624 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Incorrect |
90 ms |
57720 KB |
Output isn't correct |
| 6 |
Incorrect |
33 ms |
20496 KB |
Output isn't correct |
| 7 |
Incorrect |
27 ms |
18468 KB |
Output isn't correct |
| 8 |
Incorrect |
23 ms |
17112 KB |
Output isn't correct |
| 9 |
Incorrect |
416 ms |
60620 KB |
Output isn't correct |
| 10 |
Incorrect |
23 ms |
17540 KB |
Output isn't correct |
