27980번 - 문자열 게임

문제

건덕이는 문자가 일렬로 적혀있는 보드에서 게임을 하고 있다. 보드에는 $N$ 개의 알파벳 대문자가 나란히 적혀있다. 건덕이는 또 다른 $M$ 자리 영어 단어를 가지고 게임을 진행한다.

우선 보드의 한 지점에서 첫 번째 문자가 보드의 문자와 일치하는지 확인한다. L(왼쪽) 또는 R(오른쪽) 방향으로 이동한 후에 다음 문자와 보드의 문자가 일치하는지 확인한다. 일치할 경우 점수를 1점 얻는다. 단, 이동한 후 보드 바깥으로 벗어날 수 없다. 건덕이가 가지고 있는 단어의 끝에 도달하면 게임을 종료한다.

예를 들어, 보드에 "KONKUK" 이라는 문자가 적혀있고, "KONDUCK" 이라는 단어로 게임을 시작한다면, 2번째 문자부터 RRRRLL 순으로 이동한다면 마지막 1개의 문자만이 일치해 점수를 1점 얻는다. 최대 점수를 얻으려면, 1번째 문자부터 RRRRLR 순으로 이동하면 된다. 이 경우 "KONU"가 일치하여 점수를 4점 얻는다.

보드와 가지고 있는 단어가 주어졌을 때, 건덕이가 얻을 수 있는 최대 점수를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 보드의 길이와 건덕이가 가지고 있는 문자열의 길이를 나타내는 정수 $N, M$이 공백으로 구분되어 주어진다. $( 2 \le N, M \le 5,000円 )$

둘째 줄에는 보드의 문자가 순서대로 주어진다.

셋째 줄에는 가지고 있는 문자열이 주어진다.

이 때, 두 문자열은 모두 알파벳 대문자로만 구성되어 있다.

출력

건덕이가 얻을 수 있는 최대 점수를 출력한다.

제한

힌트