{"problem":{"name":"Common Prefixes","description":{"content":"Let the **similarity** $f(X,Y)$ between two strings $X$ and $Y$ be the length of their longest common prefix.   For example, the similarity between `abc` and `axbc` is $1$, and the similarity between ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc213_f"},"statements":[{"statement_type":"Markdown","content":"Let the **similarity** $f(X,Y)$ between two strings $X$ and $Y$ be the length of their longest common prefix.  \nFor example, the similarity between `abc` and `axbc` is $1$, and the similarity between `aaa` and `aaaa` is $3$.\nYou are given a string $S$ of length $N$. Let $S_i$ be the suffix of $S$ beginning with the $i$\\-th character of $S$. For each $k=1,\\ldots,N$, find $f(S_k,S_1)+f(S_k,S_2)+\\ldots+f(S_k,S_N)$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^6$\n*   $S$ is a string of length $N$ consisting of lowercase English letters.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc213_f","tags":[],"sample_group":[["3\nabb","3\n3\n2\n\n$S_1$ is `abb`, $S_2$ is `bb`, and $S_3$ is `b`.\n\n*   For $k=1$: $f(S_1,S_1)+f(S_1,S_2)+f(S_1,S_3)=3+0+0=3$.\n*   For $k=2$: $f(S_2,S_1)+f(S_2,S_2)+f(S_2,S_3)=0+2+1=3$.\n*   For $k=3$: $f(S_3,S_1)+f(S_3,S_2)+f(S_3,S_3)=0+1+1=2$."],["11\nmississippi","11\n16\n14\n12\n13\n11\n9\n7\n4\n3\n4"]],"created_at":"2026-03-03 11:01:13"}}