C 언어로 구현하는 Naive 패턴 검색 알고리즘 완벽 가이드

C에서의 패턴 매칭은 하나의 문자열 안에 다른 문자열이 존재하는지 찾는 작업입니다. 예를 들어, "algorithm"이라는 문자열이 "naive algorithm" 문자열 내에 포함되어 있는지 확인하고, 발견되면 해당 위치(인덱스)를 출력합니다. 이를 위해 두 개의 문자 배열을 받아 일치하면 위치를 반환하고, 그렇지 않으면 -1을 반환하는 함수를 작성할 수 있습니다.

입력 및 출력 예시

Input: txt = "HERE IS A NICE CAP"
    pattern = "NICE"
Output: Pattern found at index 10

Input: txt = "XYZXACAADXYZXYZX"
    pattern = "XYZX"
Output: Pattern found at index 0
    Pattern found at index 9
    Pattern found at index 12

Naive 패턴 검색이란?

Naive(단순) 패턴 검색 방식은 비교적 단순하지만 비효율적인 알고리즘으로, 한 문자열이 다른 문자열 내 어디에 나타나는지 확인하기 위해 가능한 모든 위치를 하나씩 차례대로 검사합니다.

Naive 알고리즘의 시간 복잡도는 O(mn)입니다. 여기서 m은 검색할 패턴의 길이, n은 원본 문자열(텍스트)의 길이를 의미합니다.

패턴 검색은 컴퓨터 과학에서 매우 중요한 문제입니다. 메모장이나 워드 파일, 브라우저, 데이터베이스 등에서 문자열을 검색할 때마다 패턴 검색 알고리즘이 사용되어 검색 결과를 표시해 줍니다.

알고리즘 동작 원리

naive_algorithm(pattern, text)

입력 − 검색 대상 텍스트와 패턴

출력 − 패턴이 텍스트 내에 존재하는 위치들

Start
    pat_len := 패턴의 길이
    str_len := 문자열의 길이
    for i := 0 to (str_len - pat_len), do
        for j := 0 to pat_len, do
            if text[i+j] ≠ pattern[j], then
                break
    if j == patLen, then
        패턴이 발견된 위치 i 출력
End

C 언어 구현 예제

#include <stdio.h>
#include <string.h>
int main (){
    char txt[] = "tutorialsPointisthebestplatformforprogrammers";
    char pat[] = "a";
    int M = strlen (pat);
    int N = strlen (txt);
    for (int i = 0; i <= N - M; i++){
        int j;
        for (j = 0; j < M; j++)
            if (txt[i + j] != pat[j])
        break;
        if (j == M)
            printf ("Pattern matches at index %d \n", i);
    }
    return 0;
}

실행 결과

Pattern matches at 6
Pattern matches at 25
Pattern matches at 39

위 코드는 텍스트 전체를 처음부터 끝까지 순회하면서 각 위치에서 패턴과 일치하는지 확인합니다. 외부 루프는 시작 위치를 결정하고, 내부 루프는 해당 위치부터 패턴 길이만큼 문자를 비교합니다. 모든 문자가 일치하면 해당 인덱스가 출력됩니다.