구간 성분 > 문제은행

본문 바로가기


알고리즘 문자열

2918 : 구간 성분

제한시간: 1Sec    메모리제한: 128mb
해결횟수: 28회    시도횟수: 358회   



매 초마다 신호를 발생시키는 두 장치 A, B가 있다. 이 신호는 알파벳 소문자의 서열로 표현된다.
A, B로 부터 발생한 신호를 서열로 표시한 SA, SB의 예는 다음과 같다.


SA = [ a, f, c, d, r, d, e, s, d, e, f, w, s, z, r ]
SB = [ g, e, d, s, r, d, d, e, m, z, r ]


신호 서열의 어떤 구간에 포함된 문자의 종류와 개수가 순서에 상관없이 동일하면 이 두 ‘구간의성분’은 같다고 한다. 아래에서 박스로 표시된 부분은 두 신호 SA, SB에서 성분이 같은 구간을 나타내고 있다.


efc6e5f9d670c6da62174cf11a66a8c2_1449740 


즉 위의 예와 같이 성분이 같은 구간의 길이는 두 서열에서 반드시 같아야 한다. 그리고 같은 성분의 구간은 하나 이상 존재할 수 있다. 우리는 두 신호 서열에 각각 존재하는 같은 성분 구간 중에서 가장 긴 것을 찾으려고 한다.


표준 입력으로 다음의 정보가 주어진다.
첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로 각각 주어진다.
이 문자열은 영문 소문자로만 구성되어 있다. 두 입력 문자열의 크기 N,M 의 범위는 5≤N,M≤1,500이다.


표준 출력으로 두 서열에서 같은 성분을 가진 구간 중에서 가장 긴 구간을 찾아, 그 구간의 길이를 출력해야 한다.

부분문제의 제약 조건
• 부분문제 1: 전체 점수 100점 중 7점에 해당하며 N,M≤100 이다.
• 부분문제 2: 전체 점수 100점 중 23점에 해당하며 N,M≤500 이다.
• 부분문제 3: 전체 점수 100점 중 31점에 해당하며 N,M≤1,000 이다.
• 부분문제 4: 전체 점수 100점 중 39점에 해당하며 N,M≤1,500 이다.

[Copy]
xraphy
edgeedgem
[Copy]
0


[Copy]
afcdrdesdefwszr
gedsrddemzr
[Copy]
7


[Copy]
computersystem
sesystuercomplexity
[Copy]
11




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.