#include <iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<deque>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<numeric>
#include<bitset>
#include<iomanip>
#include<cstdlib>
#include<time.h>
#include <functional>
#include <chrono>
#include <thread>
#include <fstream>
#include <random>
using namespace std;
#ifdef _DEBUG
#define prnt(a) cout<<#a<<"="<<a<<endl
#else
#define prnt(a) (void)0
#endif // _DEBUG
#ifdef _MSC_VER
# include <intrin.h>
# define __builtin_popcount __popcnt
#endif
#define ull unsigned long long
#define ll long long
#define ld long double
#define INF (1LL<<30)
#define INFLL (1LL<<62)
#define MOD 1000000007
#define MOD2 998244353
#define rep(i,st,en) for(ll i=(st);i<(en);++i)
#define vld vector<ld>
#define vll vector<ll>
#define vvll vector<vll>
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define VS vector<string>
#define MY_PI 3.141592653589793238462643383279502884L
#define all(v) (v).begin(), (v).end()
#define rd(...) __VA_ARGS__; read(__VA_ARGS__)
#define rdv(value,...) value(__VA_ARGS__);cin >> value
template <class T> auto& operator>>(istream& is, vector<T>& xs) {
for (auto& x : xs) is >> x;
return is;
}
template <class T> auto& operator<<(ostream& os, vector<T>& xs) {
int sz = xs.size();
rep(i, 0, sz) os << xs[i] << " \n"[i + 1 == sz];
return os;
}
template <class T, class Y> auto& operator<<(ostream& os, pair<T, Y>& xs) {
os << "{" << xs.first << ", " << xs.second << "}";
return os;
}
template <class T, class Y> auto& operator>>(istream& is, vector<pair<T, Y>>& xs) {
for (auto& [x1, x2] : xs) is >> x1 >> x2;
return is;
}
template <class ...Args>
auto& read(Args & ...args) { return (cin >> ... >> args); }
#define write(...) writemy(__VA_ARGS__);cout<<"\n"
void writemy() {}
template <typename Head, class ...Args>
void writemy(const Head& head, const Args & ...args) {
cout << head << " ";
writemy(args...);
}
void solve(ll test) {
ll rd(n);
vvll e(n);
ll p = 1069;
//l urttai h hashtai baival ene omnoh ni
map<pll, vll> mp;
vll deg(n, 0);
rep(i, 0, n) {
string rd(s);
ll m = s.size();
ll h1 = 0;
ll h2 = 0;
rep(j, 0, m) {
h1 = (h1 * p + s[j]) % MOD;
h2 = (h2 * p + s[m - 1 - j]) % MOD;
if (h1 == h2) {
for (auto v : mp[{j + 1, h1}]) {
e[v].push_back(i);
deg[i]++;
}
}
}
mp[{m, h1}].push_back(i);
}
queue<ll> q;
vll d(n, 1);
rep(i, 0, n) {
if (deg[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
ll u = q.front();
q.pop();
for (auto v : e[u]) {
deg[v]--;
if (deg[v] == 0) {
q.push(v);
d[v] = max(d[v], d[u] + 1);
}
}
}
ll ans = 0;
rep(i, 0, n) ans = max(ans, d[i]);
cout << ans << "\n";
}
int main() {
//initFacts(100, MOD2);
//findPrimes(400000);
//freopen("four_in_a_burrow_input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test = 1;
//cin >> test;
for (int t = 1; t <= test; t++)
solve(t);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |