1787번 - 문자열의 주기 예측 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 1506 | 495 | 360 | 31.915% |
문제
알파벳 소문자들로만 이루어진 문자열을 생각하자. 이런 문자열을 읽어 나가다 보면, 문자열의 주기가 예측되는 순간이 있다. 다음과 같은 문자열을 예로 들어 보자.
a b a b a b a
이 문자열을 네 번째 문자까지의 문자열 'a b a b'와, 그 뒤에 남은 'a b a'로 나누어 생각해 볼 수 있다. 이렇게 하면 뒤쪽 문자열은 앞쪽 네 개의 문자 중 세 번째 문자까지가 반복되다가 끝나는 꼴이다.
a b a b a b a
또한, 여섯 번째 문자까지의 문자열 'a b a b a b'와, 그 뒤에 남은 'a'로 나누어서 생각할 수도 있다. 이 경우에도 뒤쪽 문자열은 앞쪽 문자열이 반복되다가 끝나는 꼴이다.
즉, 예시된 문자열은 'a b a b'혹은, 'a b a b a b'가 반복되는 문자열의 일부라고 예상할 수 있는 것이다. 단, 이러한 추정에서 뒤쪽 문자열이 앞쪽 문자열보다 길면 안 된다. 예를 들어 'a b'는 이 문자열의 주기로 예측하기에는 너무 짧다.
이제는 어떤 문자열 S에 대해, 첫 번째 문자부터, i번째 문자까지로 이루어진 부분 문자열 Si를 생각해 보자. 모든 각각에 대해, 위에 예시된 것처럼 문자열의 주기를 추정할 수 있다. 우리가 관심 있는 것은 이렇게 각각에 Si에 대해 추정할 수 있는 주기 중 가장 긴 것의 길이이다. 이를 Pi라고 하자. 예시된 문자열에서 P7은 4와 6중 최댓값인 6이 된다.
길이가 n인 문자열 S가 주어졌을 때, P1 + P2 + ... + Pn을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 문자열 S의 길이 n이 주어진다. (1 ≤ n ≤ 1,000,000) 둘째 줄에 문자열 S가 공백 없이 주어진다.
출력
첫째 줄에, P1 + P2 + ... + Pn의 값을 출력한다.
예제 입력 1
8 babababa
예제 출력 1
24
힌트
P8 = 6, P7 = 6, P6 = 4, P5 = 4, P4 = 2, P3 = 2, P2 = 0, P1 = 0
출처
Olympiad > Polish Olympiad in Informatics > POI 2005/2006 > Stage 1 2번
- 문제를 번역한 사람: author10
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호