다음 C 코드에 해당하는 문자열 탐색 방법은? (단, s1은 입력 문자… | [7급 국가직 알고리즘] 24년 1회차 기출문제 상세 페이지

다음 C 코드에 해당하는 문자열 탐색 방법은? (단, s1은 입력 문자열, s2는 s1에서 찾고자 하는 패턴 문자열이고, n1은 s1의 길이, n2는 s2의 길이를 나타낸다)
int match(char *s1, char *s2) {
    int pt = 0, p = 0;
    while(pt != n1 && p != n2) {
        if (s1[pt] == s2[p]) {
            pt++;
            p++;
        } else {
            pt = pt - p + 1;
            p = 0;
        }
    }
    if (p == n2) return pt-p;
    else return -1;
}

브루트－포스(brute-force) 알고리즘

라빈－카프(Rabin-Karp) 알고리즘

오토마타를 이용한 매칭 알고리즘

보이어－무어(Boyer-Moore) 알고리즘

이 코드는 브루트-포스(brute-force) 알고리즘이다.
문자가 일치하면 두 포인터를 함께 전진하고, 불일치하면 pt = pt - p + 1로 이번 비교 시작 위치의 다음 칸으로 되돌아가 패턴을 처음(p = 0)부터 다시 비교한다. 모든 시작 위치를 하나씩 시도하므로 최악 $O(n_1 n_2)$이다.
라빈-카프는 패턴과 텍스트 구간의 해시값을 비교하는데, 코드에 해시 계산이 없다.
오토마타 매칭은 상태 전이표를 미리 만들어 텍스트를 되돌아가지 않고 한 번 훑는데, 코드는 pt를 뒤로 되돌린다.
보이어-무어는 패턴을 오른쪽 끝부터 비교하고 불일치 문자 정보로 크게 건너뛰는데, 코드는 왼쪽부터 비교하고 한 칸씩만 이동한다.