시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 36 13 11 50.000%

문제

문자열 S = S1S2...S|S|가 주어진다. |S|는 문자열 S의 길이이며, Si는 i번째 글자이다.

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

Prefix와 Suffix가 같은 문자열 중에서 그러한 문자열이 S의 부분 문자열로 몇 번 등장하는지 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 Prefix와 Suffix가 같은 문자열의 개수 K를 출력한다.

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

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

예제 입력

ABACABA

예제 출력

3
1 4
3 2
7 1

예제 입력 2

AAA

예제 출력 2

3
1 3
2 2
3 1

힌트