Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- #define pb push_back
- const int N = 6e5;
- int n;
- map<ll, ll> dp;
- vector<string> v;
- ll pw[N], ans;
- const ll mod = 1e9 + 7;
- const ll p = 29;
- main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- cin >> n;
- v.resize(n);
- for (int i = 0; i < n; ++i) cin >> v[i];
- sort(v.begin(), v.end(), [&](string a, string b) {
- return a.size() < b.size();
- });
- pw[0] = 1;
- for (int i = 1; i < N; ++i) {
- pw[i] = (pw[i - 1] * p) % mod;
- }
- for (auto d : v) {
- ll hsh = (d[0] - 'A' + 1);
- ll cnt = dp[hsh];
- for (int i = 1; i + 1 < (int)d.size(); ++i) hsh = (hsh + (d[i] - 'A' + 1) * pw[i] % mod) % mod, cnt = max(cnt, dp[hsh]);
- hsh = 0;
- for (int i = (int)d.size() - 1; i > 0; --i) hsh = (hsh * p % mod + (d[i] - 'A' + 1)) % mod, cnt = max(cnt, dp[hsh]);
- hsh = 0;
- for (int i = 0; i < (int)d.size(); ++i) hsh = (hsh + (d[i] - 'A' + 1) * pw[i] % mod) % mod;
- if (dp[hsh] != 0) dp[hsh] += 1;
- else dp[hsh] = cnt + 1;
- ans = max(ans, dp[hsh]);
- }
- cout << ans << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement