漫长悄悄话

Luogu

IDLGP10271

Time2000ms

Memory512MB

DifficultyP5

一些前置定义： - $\text{Rev}(S):$ $S_{|S|},S_{|S|-1},\dots,S_1$ 顺次相连形成的字符串。即将 $S$ 翻转。 - $\text{lcp}(i,j):$ 第 $i$ 个位置开始的后缀与第 $j$ 个位置开始的后缀的最长公共前缀**对应的字符串**。 - $\text{lcs}(i,j):$ 第 $i$ 个位置结束的前缀与第 $j$ 个位置结束的前缀的最长公共后缀**对应的字符串**。 - $\text{LCP}(S,T):$ $S$ 和 $T$ 的最长公共前缀。 ---- 给出长度为 $n$ 的字符串 $S$，求： $$\max\limits_{1 \le i < j \le n}\{\text{LCP}(\text{Rev}(\text{lcs}(i,j)),\text{lcp}(i,j))\}$$ ## Input 第一行一个整数 $n$。第二行一个长度为 $n$ 的字符串 $S$。 ## Output 输出为一个数，即答案。 [samples] ## Background > 故事从哪一页起始？ > > 小石头，红土地，遥远的火。 > > 摸索的轮廓，夜空之中，扑火的人。 > > 手与手的相握，心与心碰触。 > > 涌动在喉咙深沉，我温暖的火。 ## Note ### 样例一解释 $\text{lcp}(3,7):$ `bba`。 $\text{lcs}(3,7):$ `abb`。 $\text{LCP}(\text{Rev}(\texttt{\color{blue}abb}),\texttt{\color{blue}bba}):$ `bba`。可以证明，没有比 $i=3,j=7$ 更优的方案。 ### 数据范围与约束对于 $30\%$ 的数据，$1 \le n \le 2\times 10^3$。对于 $60\%$ 的数据，$1 \le n \le 10^5$。对于另外 $10\%$ 的数据，$\forall 1 \le i \le n-2,S_{i}\not=S_{i+2}$。对于 $100\%$ 的数据 $1 \le n \le 10^6$，输入均为整数和小写字母。

Samples

Input #1

9
abbbabbba

Output #1

API Response (JSON)

{
  "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$ 个位置结束的前...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments