13576번 - Prefix와 Suffix

문제

문자열 S = S₁S₂...S_|S|가 주어진다. |S|는 문자열 S의 길이이며, S_i는 i번째 글자이다.

• 문자열 S의 부분 문자열 S[i..j] (1 ≤ i ≤ j ≤ |S|)는 S_iS_i+1...S_j 이다.
• 문자열 S의 길이가 l (1 ≤ l ≤ |S|)인 Prefix는 S[1..l] 이다.
• 문자열 S의 길이가 l (1 ≤ l ≤ |S|)인 Suffix는 S[|S|-l+1..|S|] 이다.

S의 Prefix인 동시에 Suffix인 문자열을 찾고, 그러한 문자열이 S의 부분 문자열로 몇 번 등장하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. (1 ≤ |S| ≤ 100,000)

출력

첫째 줄에 S의 Prefix인 동시에 Suffix인 문자열의 개수 K를 출력한다.

다음 K개의 줄에는 l_i와 c_i를 출력한다. 여기서 l_i는 길이가 l_i인 Prefix가 길이가 l_i인 Suffix와 일치하고, 문자열 S의 부분 문자열로 c_i번 등장한다는 의미이다.

l_i가 증가하는 순서대로 출력해야 한다.

제한

힌트