깜직한 고양이는 작명하는데 아주 유명해서 , 많은 커플들이 바이트랜드 나라로 몰려와서 태어나는 아이들의 이름을 지어주기를 요청한다. 그들은 이름을 잘 지어서 , 태어난 아이가 명성을 얻기를 바란다. 이름을 짓는 작업은 따분한 작업이어서 혁신적인 마인드를 가진 고양이는 쉽지만 아주 기막힌 알고리즘을 고안 했다.

• Step1. 아버지의 이름과 어머니의 이름을 합쳐서 하나의 새로운 문자열 S 를 생성한다.
• Step2. 이 문자열 S 에서 prefix(접두어) 도 되고 suffix(접미어) 도 되는 문자열을 찾는다.

예로 아버지의 이름이 ala 이고 어머니의 이름이 la 이면 합친 문자열 S = alala 이다. 이 문자열에서 prefix 와 suffix 가 동시에 되는 문자열은

• a
• ala
• alala

문자열을 받아 prefix 와 suffix 가 동시에 가능한 문자열을 크기를 구하는게 문제이다.

입력

출력

입출력 예

입력

ababcababababcabab

출력

2 4 9 18

입력

aaaaa

출력

1 2 3 4 5

출처:POJ Monthly--2006.01.22,Zeyuan Zhu(2752)