프로그래밍 게시판이 생겼군요
기념(?)으로 문제 하나 풀어봐요
Q1. 유전자 연구
똑똑한 과학자인 창식이는 최근 유전자에 대한 흥미가 생겨서 그에 대해 연구 중이다. 창식이는 여러 생물의 유전자의 공통점과 차이점에 대한 연구를 하고 있는데, 창식이는 유전자들을 잘 보다가 유전자들끼리 공통된 부분이 있다는 사실을 발견하였다.
예를 들어서 AAATTCAGG 라는 유전자와 CATTCATGGG 라는 유전자는 둘 다 ATTCA 라는 공통 부분을 가지고 있다는 사실을 알 수 있다.
공통 부분은 오로지 연속된 유전자만 가능하며, 길이가 2개 이상이어야 한다.
이러한 사실에 흥미를 가지게 된 창식이는 3개의 유전자에서 공통된 부분을 찾는 연구를 하기로 하였으나, 갑작스러운 귀찮음의 습격으로 인해 연구를 하지 못하고있다. 유전자 연구를 하는 창식이를 도와주도록 하자.
입력:
3줄에 걸쳐서 입력이 들어온다.
각 줄은 대문자 ATCG로만 이루어진 공백없는 문자열이 들어온다.
문자열은 최대길이가 20만까지 가능하다.
출력:
3개의 유전자에서 가장 긴 공통 부분 유전자를 출력하도록 하자.
만약 가장 긴 공통 부분 유전자가 여러 개 있다면 그 중 아무거나 출력해도 좋다.
만약 공통 부분 유전자가 없다면, Impossible 을 출력하도록 하자.
창식이는 성격이 급하므로 프로그램에서 1초안에 답이 나오기를 바란다. 최대한 빠르게 짜보도록 하자.
예제1)
입력 :
CATTTAAA
GATTTAG
CCCATTTGG
출력 :
ATTT
예제2)
입력 :
AAAAATTT
GGGGAGG
CCCCACC
출력 :
Impossible
예제3)
입력:
ATATATA
ATATAT
TATATA
출력:
TATAT
