IOI 2003 day1 2- 코드비교(Comparing Code) > 문제은행 : 정보올림피아드&알고리즘




2084 : 코드비교(Comparing Code)

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
0 회   
시도횟수
1 회   

문제

라신 비즈니스 네트워크(이하 라비네) 사는, 휴리스틱 알고리즘 언어(이하 휴알) 사를 상대로 소송을 제기했다. 

자신의 라비네 유닉스(TM)의 소스 코드를 휴알 사가 자신의 오픈 소스 운영체제인 휴알닉스에 무단 도용했다는 것이다.

라비네와 휴알은 모두, "변수A = 변수B + 변수C" 꼴의 구문이 한 줄에 하나씩 오는 형태의 프로그래밍 언어를 사용한다.

등호와 +의 앞뒤에는 모두 공백이 한 칸 있으며, 변수A 앞에는 공백이 없다. 한 줄에 같은 변수 이름이 여러 번 등장할 수도 있다.

변수는 로마자 알파벳 대문자가 최소 한 자, 최대 여덟 자 모인 형태이다.

라비네 측은 휴알이 자사의 소스 코드의 한 부분을 뭉텅(띄엄띄엄이 아니라 연속적으로) 베껴서 그들의 코드의 일부로 삽입한 뒤,

다음과 같은 방법으로 변형만 했을 것이라고 주장한다.

베꼈다는 티를 내지 않기 위해 한 변수 이름을 다른 것으로 모두 바꾼다. 물론, 서로 다른 이름이던 변수들을 같은 이름으로 통합하지는 않는다.

덧셈은 교환 법칙이 성립하기 때문에, 베낀 코드 중에서 어떤 줄은 우항의 변수 배열 순서를 바꾼다. 

(예를 들어 A = B + C를 A = C + B로.)하지만 코드의 실행 순서 자체를 바꾸지는 않는다.

라비네 사와 휴알 사의 소스 코드를 보고, 휴알 사가 위의 조건을 만족하면서 라비네 사 코드를 최대 얼마나 베꼈을 것인지 추정하는 프로그램을 작성하시오.

휴알 사의 코드 중 어느 부분(전부일 수도 있음)이 라비네 코드의 어느 부분을 베낀 것인지는 알 수 없으므로, 프로그램이 판단해야 한다.


입력형식

첫 줄에는 R과 H가 있다. (공백으로 구분, 1<=R<=1,000, 1<=H<=1,000) 각각 라비네 사와 휴알 사의 소스 코드의 길이를 의미한다. 그 뒤 R 줄에는 라비네 사의 프로그램이 있으며, 다음 H 줄에는 휴알 사의 프로그램이 있다.


출력형식

휴알 사가 라비네 사의 코드를 베껴서 변형했을 것이라 추정되는 가장 긴 연속적인 부분의 줄 수를 출력한다.


입력 예

4 3
RA = RB + RC
RC = D + RE
RF = RF + RJ
RE = RF + RF
HD = HE + HF
HM = HN +D
HN = HA + HB

출력 예

2

Hint!

예제 입력에서 라비네 프로그램의 1-2째 줄이 휴알 프로그램의 2-3째 줄과 일치한다. 원본 프로그램에서 RA가 HM으로, RB가 D로, RC가 HN으로, D가 HA로, RE가 HB로 바뀐 것이다. 하지만 세 줄이 연달아 일치하는 부분은 없다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP