샘(Sam)은 클루(Clu)가 열어 두었을 가능성이 있는 외부 세계로 향하는 통신 경로를 발견했지만, 작동하는지 확인하기 위해서는 올바른 암호를 찾아야 합니다.
그는 또한 클루가 그리드(Grid) 세계의 수백만 개 게이트의 암호를 모두 기억하는 데 어려움을 겪어, 보통 암호를 근처 어딘가에 적어 둔다는 것을 알고 있습니다. 그러나 클루는 암호를 직접 적지 않고, 게이트 옆 벽에 적힌 여러 개의 문자열 속에 암호를 인코딩해 두었습니다.
암호를 해독하는 첫 번째 단계는 벽에 적힌 모든 문자열의 가장 긴 감소 접미사(LDS)를 찾는 것입니다. 샘은 그 후 암호를 구성하는 방법을 알고 있지만, 이 첫 번째 단계를 위해 당신의 도움이 필요합니다.
문자열의 감소 접미사(Decreasing Suffix)는 접미사 내의 각 문자가 다음 문자보다 더 큰 접미사입니다. 문자열의 LDS는 그러한 접미사 중에서 가장 긴 것입니다.
예시: 문자열 "abcdbca"의 LDS는 "ca"입니다.
입력
테스트 데이터 파일의 첫 번째 줄에는 테스트 케이스의 수 ($\le 50$)가 포함됩니다.
그 후, 각 줄에는 길이가 100자 미만인 입력 문자열이 포함됩니다.
입력 문자열은 'a'부터 'z'까지의 소문자만 포함한다고 가정할 수 있습니다.
출력
각 테스트 케이스에 대해, 입력 문자열의 가장 긴 감소 접미사를 찾아 아래 예시와 같이 출력하십시오.
blackbee4 1년 전
샘(Sam)은 클루(Clu)가 열어 두었을 가능성이 있는 외부 세계로 향하는 통신 경로를 발견했지만, 작동하는지 확인하기 위해서는 올바른 암호를 찾아야 합니다.
그는 또한 클루가 그리드(Grid) 세계의 수백만 개 게이트의 암호를 모두 기억하는 데 어려움을 겪어, 보통 암호를 근처 어딘가에 적어 둔다는 것을 알고 있습니다. 그러나 클루는 암호를 직접 적지 않고, 게이트 옆 벽에 적힌 여러 개의 문자열 속에 암호를 인코딩해 두었습니다.
암호를 해독하는 첫 번째 단계는 벽에 적힌 모든 문자열의 가장 긴 감소 접미사(LDS)를 찾는 것입니다. 샘은 그 후 암호를 구성하는 방법을 알고 있지만, 이 첫 번째 단계를 위해 당신의 도움이 필요합니다.
문자열의 감소 접미사(Decreasing Suffix)는 접미사 내의 각 문자가 다음 문자보다 더 큰 접미사입니다. 문자열의 LDS는 그러한 접미사 중에서 가장 긴 것입니다.
예시: 문자열 "abcdbca"의 LDS는 "ca"입니다.
입력
테스트 데이터 파일의 첫 번째 줄에는 테스트 케이스의 수 ($\le 50$)가 포함됩니다.
그 후, 각 줄에는 길이가 100자 미만인 입력 문자열이 포함됩니다.
입력 문자열은 'a'부터 'z'까지의 소문자만 포함한다고 가정할 수 있습니다.
출력
각 테스트 케이스에 대해, 입력 문자열의 가장 긴 감소 접미사를 찾아 아래 예시와 같이 출력하십시오.