{"problem":{"name":"漫长悄悄话","description":{"content":"一些前置定义： - $\\text{Rev}(S):$ $S_{|S|},S_{|S|-1},\\dots,S_1$ 顺次相连形成的字符串。即将 $S$ 翻转。 - $\\text{lcp}(i,j):$ 第 $i$ 个位置开始的后缀与第 $j$ 个位置开始的后缀的最长公共前缀**对应的字符串**。 - $\\text{lcs}(i,j):$ 第 $i$ 个位置结束的前缀与第 $j$ 个位置结束的前","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10271"},"statements":[{"statement_type":"Markdown","content":"一些前置定义：\n\n- $\\text{Rev}(S):$ $S_{|S|},S_{|S|-1},\\dots,S_1$ 顺次相连形成的字符串。即将 $S$ 翻转。\n\n- $\\text{lcp}(i,j):$ 第 $i$ 个位置开始的后缀与第 $j$ 个位置开始的后缀的最长公共前缀**对应的字符串**。\n\n- $\\text{lcs}(i,j):$ 第 $i$ 个位置结束的前缀与第 $j$ 个位置结束的前缀的最长公共后缀**对应的字符串**。\n\n- $\\text{LCP}(S,T):$ $S$ 和 $T$ 的最长公共前缀。\n----\n\n给出长度为 $n$ 的字符串 $S$，求：\n\n$$\\max\\limits_{1 \\le i < j \\le n}\\{\\text{LCP}(\\text{Rev}(\\text{lcs}(i,j)),\\text{lcp}(i,j))\\}$$\n\n## Input\n\n第一行一个整数 $n$。\n\n第二行一个长度为 $n$ 的字符串 $S$。\n\n## Output\n\n输出为一个数，即答案。\n\n[samples]\n\n## Background\n\n> 故事从哪一页起始？\n>\n> 小石头，红土地，遥远的火。\n>\n> 摸索的轮廓，夜空之中，扑火的人。\n>\n> 手与手的相握，心与心碰触。\n>\n> 涌动在喉咙深沉，我温暖的火。 \n\n## Note\n\n### 样例一解释\n\n$\\text{lcp}(3,7):$ `bba`。\n\n$\\text{lcs}(3,7):$ `abb`。\n\n$\\text{LCP}(\\text{Rev}(\\texttt{\\color{blue}abb}),\\texttt{\\color{blue}bba}):$ `bba`。\n\n可以证明，没有比 $i=3,j=7$ 更优的方案。\n\n### 数据范围与约束\n\n对于 $30\\%$ 的数据，$1 \\le n \\le 2\\times 10^3$。\n\n对于 $60\\%$ 的数据，$1 \\le n \\le 10^5$。\n\n对于另外 $10\\%$ 的数据，$\\forall 1 \\le i \\le n-2,S_{i}\\not=S_{i+2}$。\n\n对于 $100\\%$ 的数据 $1 \\le n \\le 10^6$，输入均为整数和小写字母。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10271","tags":[],"sample_group":[["9\nabbbabbba","3"]],"created_at":"2026-03-03 11:09:25"}}