대엉코딩

0. string

- character의 sequence 이다.

- string의 예시로서는

  -> HTML문서

  -> DNA sequence

  -> 등등....매우 많다.

- 아스키코드, binary alphabets, DNA alphabets( {A,C,G,T} )

- 보통 TEXT에서 PATTERN과 일치하는 SubString(그 위치)를 찾는 문제가 많다.

- 검색엔진, 텍스트 에디터, 생물학적 조사 등 을 할 때 주요하게 사용된다. 

1. 개요

- 가장 간단하고 naive한 방식의 알고리즘 이다.

- 텍스트의 위치 가능한 모든 자리에 PATTERN을 매치시켜 비교과정을 거친다.

- 비교과정 중 완벽하게 매치하거나 남은 텍스트의 길이보다 패턴의 길이가 더 길어질 경우 비교를 멈춘다.

2. 시간복잡도

- 워낙 간단해서 의사코드를 기재하진 않았지만 복잡도 분석을 해보면

- 텍스트의 길이 (m) 패턴의 길이 (n)  이라 하면 시간 복잡도는 O(n*m)

- m의 위치 가능한 모든 자리에서 n을 비교하기 때문에 최악의 경우 O(n*m) 이다.

- 최악의 경우 중 간단한 예시를 들어보면

 -> TEXT: AAAA........B

 -> PATTERN: AAAB

-이경우 불일치가 패턴의 맨 끝에 존재하므로 패턴을 매번 비교할 때 마다 끝문자가 나타날 때 까지 비교를 해야한다.

3. 장점 및 단점

- 장점은 알고리즘 자체가 매우 간단하다.

- 패턴이나 텍스트를 Preprocessing하는 과정이 없다.

- 알파벳의 범위가 좁을 경우 (위의 경우 처럼 a,b) 성능이 떨어진다.

- 영어나 한국어처럼 글자의 종류가 매우 많을경우는 나름 brute-force도 성능이 괜찮을 수 있다.