카페의 섞인 주문 묶음

문제

한 카페는 음료 종류를 알파벳 소문자 하나로 표시한다. 주문이 접수될 때마다 음료 코드 하나를 긴 기록 문자열 S의 뒤에 붙인다. 같은 음료가 여러 번 주문되면 같은 문자가 그 횟수만큼 기록된다. 문자열의 각 위치는 음료 한 잔의 주문에 대응하며, 위치 번호는 왼쪽부터 1번으로 센다. 카페는 여러 잔을 한꺼번에 준비하는 묶음 상품을 운영한다. 묶음 상품의 구성은 문자열 P로 주어진다. P에 어떤 문자가 세 번 등장한다면 그 음료가 정확히 세 잔 필요하다는 뜻이다. P에 적힌 순서는 준비 순서를 의미하지 않는다. 따라서 두 문자열에 등장하는 각 문자의 개수가 모두 같다면 같은 구성으로 취급한다. 음료의 총수량만 같고 종류별 수량이 다르면 다른 구성이다. 관리자는 주문 기록에서 묶음 상품과 구성이 일치하는 구간을 찾으려 한다. 선택할 수 있는 구간은 반드시 S에서 연속한 위치들로 이루어져야 하며, 길이는 P의 길이와 정확히 같아야 한다. 구간 안의 주문 순서는 달라도 되지만, 구간 밖의 주문을 가져오거나 구간 안의 일부 주문을 빼는 것은 허용하지 않는다. 음료 코드의 종류별 등장 횟수가 P와 모두 일치할 때에만 그 구간을 유효한 구간이라고 부른다. 서로 다른 시작 위치를 가진 구간은 별개로 센다. 두 유효한 구간이 일부 주문을 공유하더라도 둘 다 개수에 포함한다. 이 작업은 기록을 분석하는 과정이므로, 구간을 하나 찾았다고 실제 주문 기록에서 해당 주문을 제거하지 않는다. 모든 유효한 구간의 개수와 그중 가장 먼저 시작하는 구간의 시작 위치를 구한다. 유효한 구간이 없으면 개수는 0이고 시작 위치는 -1이다.

입력

첫째 줄에 S의 길이 N과 P의 길이 M이 정수로 주어진다. 1 ≤ M ≤ N ≤ 200,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다.
셋째 줄에 길이가 정확히 M인 문자열 P가 주어진다.
두 문자열은 알파벳 소문자 a부터 z로만 이루어져 있으며 공백은 없다.

출력

유효한 구간의 개수와 가장 작은 시작 위치를 공백으로 구분하여 한 줄에 출력한다. 시작 위치는 1부터 센다. 유효한 구간이 없으면 0 -1을 출력한다.

8 3
abacbaba
aab

2 1

5 2
ccccc
ab

0 -1

4 2
aaaa
aa

3 1

출처: Devin.KR 자체 제작