[알고리즘] 나이브 문자열 검색(Naive String Search) 알고리즘

1. 개요

나이브 문자열 검색(Naive String Search)은 가장 기본적인 문자열 탐색 기법이다. 이 알고리즘은 긴 문자열 내에서 특정한 짧은 문자열(패턴)이 몇 번 등장하는지를 확인하는 데 사용된다. 

---

2. 알고리즘 개념

나이브 문자열 검색은 다음과 같은 방식으로 동작한다.

• 긴 문자열의 각 문자부터 시작하여,
• 짧은 문자열의 길이만큼 잘라서 비교하며,
• 모든 문자가 일치하면 해당 위치를 일치로 간주하고 카운트를 증가시킨다.

---

3. 동작 절차 

1. count를 0으로 초기화한다.
2. 긴 문자열의 0번째 문자부터 (긴 문자열 길이 - 짧은 문자열 길이) 위치까지 반복한다.
3. 매 반복마다:
   • 짧은 문자열의 문자를 하나씩 반복하며,
   • 긴 문자열의 i + j 번째 문자와 짧은 문자열의 j 번째 문자를 비교한다.
   • 둘 중 하나라도 다르면 비교를 중단한다.
   • 끝까지 모두 일치하면 count를 1 증가시킨다.
4. 모든 비교가 끝나면 count를 반환한다.

---

5. 자바스크립트 구현 (주석 포함)

/**
 * 나이브 문자열 검색 알고리즘
 * 긴 문자열에서 짧은 문자열이 몇 번 등장하는지 계산
 */
function naiveSearch(longStr, shortStr) {
  let count = 0; // 일치 횟수를 저장할 변수 초기화

  // 긴 문자열의 각 문자부터 짧은 문자열이 들어갈 수 있는 위치까지만 반복
  for (let i = 0; i <= longStr.length - shortStr.length; i++) {
    let match = true; // 현재 위치에서 패턴이 일치하는지 여부를 저장

    // 짧은 문자열의 각 문자와 긴 문자열의 i + j 위치 문자 비교
    for (let j = 0; j < shortStr.length; j++) {
      if (longStr[i + j] !== shortStr[j]) {
        match = false; // 하나라도 다르면 불일치로 간주
        break;         // 더 이상 비교하지 않음
      }
    }

    // 모든 문자가 일치한 경우 카운트 증가
    if (match) {
      count++;
    }
  }

  return count; // 최종 일치 개수를 반환
}

// 예시 사용
console.log(naiveSearch("ababab", "ab")); // 출력: 3

---

6. 예제 시나리오

"lorie loled"에서 "lol" 찾기

• i = 0: "lor" → 불일치
• i = 1: "ori" → 불일치
• i = 2: "rie" → 불일치
• i = 3: "ie " → 불일치
• i = 4: "e l" → 불일치
• i = 5: " lo" → 불일치
• i = 6: "lol" → 일치 → count +1
• i = 7 이후: 길이 부족으로 비교 종료
• 최종 결과: 1회 일치

 

---

7. 성능 분석

항목	설명
시간 복잡도	O(n × m) (n: 긴 문자열 길이, m: 짧은 문자열 길이)
공간 복잡도	O(1) (추가 공간 거의 없음)
장점	구현이 매우 간단하고 직관적임
단점	성능이 비효율적이며, 중복되는 비교가 많음
개선점	KMP, Rabin-Karp, Boyer-Moore 등의 고급 문자열 검색 알고리즘

---

8. 결론

나이브 문자열 검색 알고리즘은 문자열 검색의 가장 기본적인 형태이다. 성능은 떨어지지만 구조가 단순하고, 문자열 비교의 핵심 개념을 이해하기에 적합하다.