접미사 배열 1
시간 제한2초메모리 제한512 MB
길이가 같은 더 작은 문자열 중 S와 같은 접미사 배열을 갖는 것이 존재하는지 판별한다. |S|는 50 이하이다.
문제
문자열 의 번째 접미사는 의 번째 글자에서 시작해 문자열 끝까지 이어지는 부분이다. 글자 번호는 0부터 센다. 예를 들어 = "abcde"이면 0번째 접미사는 "abcde"이고 3번째 접미사는 "de"이다.
의 접미사 배열은 의 모든 접미사를 사전 순으로 정렬한 다음, 각 접미사가 시작하는 번호를 그 순서대로 적은 배열이다. 예를 들어 = "abca"이면 접미사 배열은 이다.
문자열 가 주어질 때, 와 접미사 배열이 같으면서 사전 순으로 보다 앞서는 문자열 가 존재하는지 판정하는 프로그램을 작성하시오. 의 길이는 와 같고, 도 알파벳 소문자로만 이루어진다.
입력
첫째 줄에 문자열 가 주어진다. 의 길이는 1 이상 50 이하이고, 알파벳 소문자로만 이루어져 있다.
출력
사전 순으로 보다 앞서면서 접미사 배열이 와 같은 문자열이 존재하면 1을, 존재하지 않으면 0을 출력한다.