Submission #165561

#TimeUsernameProblemLanguageResultExecution timeMemory
165561Atill83Savez (COCI15_savez)C++14
120 / 120
378 ms32848 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define endl '\n' using namespace std; const long long INF = (long long) 1e18; const int mod = (int) 1e9+7; const int MAXN = (int) 2e6+5; typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pii; typedef pair<ll,ll> pll; ll n; string s; map<pll, ll> mp; ll pw[MAXN]; ll pw2[MAXN]; ll ch[MAXN]; ll bp(ll a, ll b){ ll res = 1; while(b){ if(b % 2) res = (res * a) % mod; a = (a * a)%mod; b = b / 2; } return res; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); #ifdef Local freopen("../IO/int.txt","r",stdin); freopen("../IO/out.txt","w",stdout); #endif cin>>n; pw[0] = 1; pw2[0] = 1; for(int i = 1; i < MAXN; i++){ pw[i] = pw[i - 1]*37%mod; pw2[i] = pw2[i - 1]*43%mod; } ll ans = 0; for(int i = 0; i < n; i++){ cin>>s; ll hash = 0; ll hash2 = 0; for(int j = 0; j < (int)s.length(); j++){ hash += (int)(s[j] - 'A' + 1)*pw[j]; hash2 += (int) (s[j] - 'A' + 1)*pw2[j]; hash %= mod; hash2 %= mod; ch[j] = hash; } //cout<<"hash for: "<<s<<" "<<hash<<" "<<hash2<<endl; ll cur = mp[{hash, hash2}]; ll curH = 0; ll curH2 = 0; for(int l = 0; l < (int) s.length() - 1; l++){ ll nw = ch[l]; ll ter = ch[(int)s.length() - 1] - ch[(int)s.length() - 2 - l] + mod; ter %= mod; ter = ter*bp(pw[(int)s.length() - l - 1], mod - 2); ter %= mod; curH += pw[l]*((int)(s[l] - 'A' + 1)); curH %= mod; curH2 += pw2[l]*((int)(s[l] - 'A' + 1)); curH2 %= mod; if(nw != ter){ //cout<<s<<" "<<l<<endl; //cout<<nw<<" "<<ter<<endl; continue; } //cout<<nw<<" "<<curH<<" "<<curH2<<endl; mp[{hash, hash2}] = max(mp[{hash, hash2}], mp[{curH, curH2}] + 1); } mp[{hash, hash2}] = max(mp[{hash, hash2}], cur + 1LL); //cout<<s<<" "<<mp[{hash, hash2}]<<endl; ans = max(ans, mp[{hash, hash2}]); } cout<<ans<<endl; #ifdef Local cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "; #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...