Longest Uncommon Prefix

AtCoder

IDabc285_b

Time2000ms

Memory256MB

Difficulty—

You are given a string $S$ of length $N$ consisting of lowercase English letters. The $x$\-th $(1 \le x \le N)$ character of $S$ is $S_x$. For each $i=1,2,\dots,N-1$, find the maximum non-negative integer $l$ that satisfies all of the following conditions: * $l+i \le N$, and * for all integers $k$ such that $1 \le k \le l$, it holds that $S_{k} \neq S_{k+i}$. Note that $l=0$ always satisfies the conditions. ## Constraints * $N$ is an integer such that $2 \le N \le 5000$. * $S$ is a string of length $N$ consisting of lowercase English letters. ## Input The input is given from Standard Input in the following format: $N$ $S$ [samples]

Samples

Input #1

6
abcbac

Output #1

5
1
2
0
1

In this input, $S=$ `abcbac`.

*   When $i=1$, we have $S_1 \neq S_2, S_2 \neq S_3, \dots$, and $S_5 \neq S_6$, so the maximum value is $l=5$.
*   When $i=2$, we have $S_1 \neq S_3$ but $S_2 = S_4$, so the maximum value is $l=1$.
*   When $i=3$, we have $S_1 \neq S_4$ and $S_2 \neq S_5$ but $S_3 = S_6$, so the maximum value is $l=2$.
*   When $i=4$, we have $S_1 = S_5$, so the maximum value is $l=0$.
*   When $i=5$, we have $S_1 \neq S_6$, so the maximum value is $l=1$.

API Response (JSON)

{
  "problem": {
    "name": "Longest Uncommon Prefix",
    "description": {
      "content": "You are given a string $S$ of length $N$ consisting of lowercase English letters. The $x$\\-th $(1 \\le x \\le N)$ character of $S$ is $S_x$. For each $i=1,2,\\dots,N-1$, find the maximum non-negative int",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc285_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a string $S$ of length $N$ consisting of lowercase English letters. The $x$\\-th $(1 \\le x \\le N)$ character of $S$ is $S_x$.\nFor each $i=1,2,\\dots,N-1$, find the maximum non-negative int...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments