탠덤 반복 | cho.sh

DNA에서 뉴클레오타이드 하나 이상으로 이루어진 패턴이 바로 뒤에 한 번 더 이어져 나오면, 그 자리를 탠덤 반복이라고 부른다. 예를 들어 다음 서열을 보자.

이 서열에는 탠덤 반복이 9개 들어 있다.

정리하면, 길이가 $2L$ 인 부분 문자열의 앞쪽 $L$ 글자와 뒤쪽 $L$ 글자가 같을 때 그 부분 문자열이 탠덤 반복 하나다. 시작 위치가 다르거나 길이가 다르면 서로 다른 탠덤 반복으로 세고, 두 탠덤 반복이 겹쳐 있어도 각각 센다.

뉴클레오타이드 서열이 주어질 때 그 안에 탠덤 반복이 몇 개 있는지 구하는 프로그램을 작성하시오.

입력은 테스트 케이스 여러 개로 이루어진다. 각 테스트 케이스는 한 줄에 문자열 하나로 주어지고, 길이는 1 이상 100,000 이하이며 대문자 A, G, T, C로만 이루어진다. 이 문자열이 뉴클레오타이드 서열이다. 입력의 마지막 줄에는 0 하나만 주어진다.

각 테스트 케이스마다 서열에 들어 있는 탠덤 반복의 개수를 정수 하나로 한 줄에 출력한다. 공백은 출력하지 않고, 답과 답 사이에 빈 줄도 넣지 않는다.