작명하기
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- NAMING
- 500ms
- 65536kb
- 6290
- 1034 (16%)
-
- 출처
- 분류
문제
주의. 이 문제는 입문자용 문제가 아니며, 문자열을 다루는 알고리즘에 대한 이해를 돕기 위한 연습 문제입니다. 문제 해결을 처음 시도하시는 분들께서는 이 문제가 아니라 좌측 메뉴의 '튜토리얼' 페이지 등을 참조하시어 다른 문제를 시도하시길 권장드립니다.
아주대에 사는 외수는 작명에 능하기로 유명해서 많은 부부들이 아주대로 몰려와서 태어나는 아이들의 이름을 지어달라고 한다. 부부들은 이름은 잘 짓는게 출세에 영향을 미친다고 생각을 하고 있으며, 따라서 좋은 이름을 지어 출세하기를 기원한다. 허나 게으른 외수에게 작명은 지루한 작업이다. 효율적으로 일을 하고자 궁리하던 차에 쉽지만 기가 막힌 알고리즘을 고안하게 되었다.
외수가 개발한 작명 알고리즘은 다음과 같다.
- 아버지의 이름 뒤에 어머니의 이름을 덧붙여서 하나의 새로운 문자열 S로 만든다.
- 이 문자열 S의 접두사(prefix)도 되고 접미사(suffix)도 되는 문자열을 찾는다.
예를 들어 아버지의 이름이 'ala'고 어머니의 이름이 'la' 일 경우 S = 'ala' + 'la' = alala다. 그리고 이 문자열의 접두사이기도 하고 접미사이기도 한 문자열은 다음 세가지다.
- a
- ala
- alala
아버지와 어머니의 이름이 주어질 때, 외수의 규칙을 이용해 지어줄 수 있는 이름들을 모두 찾는 프로그램을 작성하라. 문제에서는 편의상 모든 문자열 대신, 가능한 모든 문자열의 길이를 찾는다.
입력
빈칸이 없는 영문 알파벳 소문자로 이뤄진 문자열이 입력이 두 줄 입력된다.
첫 번째 줄은 아버지의 이름이고, 두 번째 줄은 어머니의 이름이다.
두 문자열의 길이를 합쳐서 400,000 자가 넘어가는 입력은 들어오지 않는다.
출력
외수가 주어질 수 있는 이름들의 길이들을 한 줄에 출력한다.
출력되는 숫자 사이에는 정확히 공백이 하나 포함되어야 하며, 길이는 오름차순으로 출력되어야 한다.
예제 입력
ababcabababa bcabab
예제 출력
2 4 9 18
노트
