Notice
250x250
Recent Posts
Recent Comments
Link
넘치게 채우기
문자열 패턴 검색: 1 - Naive 패턴 검색 (Naive Pattern Searching) 본문
728x90
반응형
설명
Naive 패턴 검색 알고리즘은, 문자열에서 패턴을 찾는 가장 단순한 방법이다.
패턴을 텍스트 위로 하나씩 밀어서 일치하는지 확인하고, 일치하는 것이 발견되면, 1개씩 다시 밀어서 다음에 일치하는 항목을 확인한다.
코드(C++)
#include <iostream>
#include <string>
using namespace std;
void search(string &pat, string &txt) {
int M = pat.size();
int N = txt.size();
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) {
cout << "pattern found at: " << i << "\n";
}
}
}
int main() {
// Example 1
string txt1 = "AABAACAADAABAABA";
string pat1 = "AABA";
cout << "Example 1: " << endl;
search(pat1, txt1);
// Example 2
string txt2 = "agd";
string pat2 = "g";
cout << "\nExample 2: " << endl;
search(pat2, txt2);
return 0;
}
Example 1:
pattern found at: 0
pattern found at: 9
pattern found at: 12
Example 2:
pattern found at: 1
복잡도 분석
시간 복잡도: O(n * m) - n은 문자열의 길이, m은 패턴의 길이
공간 복잡도: O(1) - 인덱스 변수만을 사용
만약에 하나의 패턴만 찾는 경우라면, 시간 복잡도는 최상의 경우 O(m)이 될 수 있다.(시작 지점부터 패턴 발견)
최악에는 O(n*m)이다.(패턴이 없거나, 맨 마지막에 등장)
출처
https://www.geeksforgeeks.org/naive-algorithm-for-pattern-searching/?ref=shm
728x90
반응형
'컴퓨터과학 > 알고리즘' 카테고리의 다른 글
문자열 패턴 검색: 3 - KMP 알고리즘 (0) | 2024.09.20 |
---|---|
문자열 패턴 검색: 2 - 라빈-카프 알고리즘 (Rabin-Karp Algorithm) (0) | 2024.09.20 |
[알고리즘] 유니온-파인드(Union-Find) (0) | 2023.09.14 |
[알고리즘] 벨만포드 알고리즘 (0) | 2023.09.11 |
[알고리즘] 위상 정렬(Toplogiclal Sort) (0) | 2023.09.11 |