[알고리즘] 단순 문자열 매칭

Hyo Kyun Lee·2022년 1월 17일
0

알고리즘

목록 보기
22/45

22. 단순 문자열 매칭

특정한 글(문자열)이 있을때 그 글 안에서 하나의 문자열을 찾는 알고리즘이다.
흔히 사용하는 탐색, ctrl+F와 같이 해당 문자열 내부에서 문자열이 있는지 탐색한다.

22-1. 이중반복을 통한 문자열 단순 비교

말 그대로 단순하게 하나씩 문자열을 비교해가면서 확인한다.

parent String(탐색 문자열) 내에서 pattern String(탐색 대상)을 1차적으로 순회한다(첫번째 인덱스를 맞춰가면서 비교문자를 순회).

위와 같이 1차순회를 마친 후, pattern String과 parent String 각각의 문자를 하나하나 비교해나가는 2차순회를 진행한다.

22-2. 시간복잡도

O(N*M)의 시간복잡도를 가진다.

즉 탐색 문자열의 길이만큼 이중적으로 반복 및 순회를 진행하므로, 시간복잡도는 그에 비례하여 증가한다.

단순 문자열 매칭은 가장 직관적이고 구현하기 쉬운 코드이지만, 효율적이지 않은 알고리즘이다.

22-3. break / continue

break는 중첩반복문에서 가장 가까운 반복문에서 탈출하는 명령어이다.

이때 중첩반복문에서 바깥의 반복문을 다시 실행하고자 할 때는 continue를 작성해주어야 반복문이 실행된다.

break만 써주어도 바깥의 반복문이 실행되는 줄 알았는데, continue를 작성해주어야 중첩반복이 정상적으로 작동한다는 것을 알게되었다.

22-4. 참조자료

break, continue
https://velog.io/@sjwngjs/javascriptpython-%EC%9D%B4%EC%A4%91-for%EB%AC%B8-%ED%83%88%EC%B6%9C

0개의 댓글