No.290 1010
タグ : / 解いたユーザー数 320
作問者 :
anta
Problem Statement
You are given a string $S$ of length $N$ consisting only of 0 and 1.
Let $S[a,b]$ denote the substring obtained by concatenating the $a$-th through $b$-th characters of $S$ (both ends inclusive).
Do there exist two integers $i, j$ satisfying $1 \le i \le j$ and ${j+(j+1-i)} \le N$ such that $S[i,j] = S[{j+1},{j+(j+1-i)}]$?
Input
N S
The first line contains an integer $N (1 \le N \le 10^6)$. The second line contains a string $S$ of length $N$ consisting only of 0 and 1.
Output
Print "YES" if a pair of integers satisfying the condition in the problem statement exists, and "NO" otherwise, on one line (without the quotation marks).
Sample
Sample 1
Input
1 0
Output
NO
Sample 2
Input
2 00
Output
YES
$(i, j) = (1, 1)$ satisfies the condition in the problem statement.
Sample 3
Input
14 00110101101010
Output
YES
For example, $S[3,7] = S[8,12] = 11010$, so $(i, j) = (3, 7)$ and others satisfy the condition.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。