devbelly

문제 www.acmicpc.net/problem/20191 알고리즘 이분탐색 풀이 문자열 S와 T가 주어집니다. $T^n$을 문자열 T를 n회 반복한 문자열이라고 정의할 때, n번 반복하여 줄임말 S를 만들기 위한 최소 n을 구하는 문제입니다. 줄임말을 만들 때, 순서를 유지한다는 점에서 투포인터 전략을 떠올릴 수 있습니다. 각각을 $pt, ps$라고 해봅시다. 각 포인터가 가리키는 문자열이 일치할 때는 둘 다 1씩 더해서 다음 문자를 확인하고 다르다면 $pt$만을 증가시키고 문자열 T가 끝에 다다랐다면 다시 $pt$를 0으로 초기화 해줍니다. 이렇게 할 경우 다음과 같은 예시에서 비효율적으로 작동하게 됩니다. zzzz aaaz 즉 z가 나타나는 위치를 찾기 위해 일일이 T문자열을 탐색하는 대신, 다른 ..