시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB253664832.215%

문제

어떤 문자열 S와, S의 부분문자열 a, b, c, d가 주어졌을 때, 각각의 부분문자열 a, b, c, d가 S와 어디에서 겹쳐졌는지 구해보자. 이때, S의 어떤 위치에 있는 문자가 a, b, c, d중 하나에 속했을 때, 이 문자를 가릴 수 있다고 한다. (겹치는 것도 가능하다.)

예를 들어, S = foursubstrings이고, a = our, b = s, c = ring, d = sub라고 했을 때,

f o u r s u b s t r i n g s
  o u r                    
        s                  
                  r i n g  
        s u b              
  + + + + + +     + + + +  

가장 위의 문자열은 S이고, 그 밑에는 차례대로 a, b, c, d이다. 가장 마지막의 +는 가려진 문자를 말한다.

가려진 문자의 최솟값과 최댓값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S의 길이는 2500보다 작거나 같다. 둘째 줄부터 다섯째 줄에는 부분 문자열 a, b, c, d가 한 줄에 하나씩 차례대로 주어진다. 부분문자열의 길이는 50보다 작거나 같다. 모든 문자열은 소문자로만 이루어져 있다.

출력

첫째 줄에 가려지는 문자열의 개수의 최솟값과 최댓값을 공백을 사이에 두고 구분해서 출력한다.

예제 입력 1

abacaba
ab
ba
a
c

예제 출력 1

4 6

예제 입력 2

hello
he
l
l
o

예제 출력 2

4 5

예제 입력 3

ababababababa
ababababa
ababababa
ababababa
ababababa

예제 출력 3

9 13

예제 입력 4

foursubstrings
our
s
ring
sub

예제 출력 4

10 11

힌트

ABACaba로 가리면 4개를 가릴 수 있고 (대문자가 가려진 문자), ABACaBA로 가리면 6개를 가릴 수 있다.

출처