판교의 메타몽

문제 링크 : https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 문제 요약 1. 테스트 케이스 t개 만큼 문자열 w와 양의 정수 k가 주어집니다. 2. 문자열 w에서 어떤 문자를 정확히 k개 포함하고, 가장 짧은 연속 문자열의 길이를 구하세요. 3. 문자열 w에서 어떤 문자를 정확히 k개 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구하세요. 핵심 포인트 슬라이딩 윈도우 기법을 활용하면 됩니다...

문제 링크 : www.acmicpc.net/problem/1593 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net 이 문제는 실수를 여러번 겪었다. 처음에는 문자열 W의 조합을 next_permutation 함수로 구하여 그 값을 찾는 과정을 진행했는데, 번번히 시간초과가 나왔다. 문제를 자세히 읽어보니 W의 길이는 최대 3000, S의 길이는 최대 3,000,000이라서 시간초과가 나올 수 밖에 없는 구조임을 깨달았다. 문자열 W의 조합 3000!만 고려해도 시간초과는 정해진 ..