17
2016-Apr
[알고리즘] 문자열 검색
작성자: 
Blonix
IP ADRESS: *.148.87.98 조회 수: 1697
출처 :: https://namu.wiki/w/%EB%AC%B8%EC%9E%90%EC%97%B4%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
KMP 알고리즘 참고자료 :: http://bowbowbow.tistory.com/6
(이 링크를 참고하기 바란다)
Native String Search
그냥 가장 쉽게 생각하는 바로 그 알고리즘. 한글자씩 매치 확인을 한다. 간단하니까 대상 문자열 짧으면 쓸만함.
#include <stdio.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
typedef int BOOL;
void find_pattern(const char* pszString, const char* pszPattern)
{
int nStrLength, nPatternLength;
int i, j;
BOOL bFlag = TRUE;
nStrLength = strlen(pszString);
nPatternLength = strlen(pszPattern);
for(i = 0; i < (nStrLength - nPatternLength); ++i)
{
for(j = 0; j < nPatternLength; ++j)
{
if(pszString[i + j] != pszPattern[j])
{
break;
}
}
if(j == nPatternLength)
{
printf("The matching : %d\n", i + 1);
bFlag = FALSE;
}
}
if(bFlag)
{
printf("NONE\n");
}
}
int main(int argc, char* argv[])
{
const char* pszString = "hello hello hello hellchosun";
const char* pszPattern = "hell";
find_pattern(pszString, pszPattern);
}
Finite-state automaton based search
그냥 오토마타라고 부르기도 하며, 선형시간의 효율성을 자랑 하는 알고리즘, 후술할 KMP 알고리즘이 해당 알고리즘 보다 빠르고 더 이해하기도 쉽다. 이 알고리즘은 상태전이함수를 만들어야 하는데, 그 탐색 횟수 까지 고려해야 한다. 따라서 전체 탐색 횟수는 (n + m||), 이때, || 는 문자열에 속해있는 문자의 종류의 개수이다. 상태를 나타내는 p, 현재 문자열의 위치에 있는 문자의 종류를 나타내는 q 가 있다면, 상태전이 함수 p = [p][q] 를 n번 반복해주다가 최종 상태에 돌입하면 매칭된 위치를 출력해주면 된다. 자세한 사항은 오토마타를 참조.
Knuth-Morris-Pratt Algorithm (KMP 알고리즘)
위 참고자료에 매우 설명이 잘 되어있으니 링크가 살아있다면 그걸 보는걸 추천한다.
사실 그 페이지를 복사해오려 했는데 표가 잔뜩 들어가서 html 용량이 너무 커지다보니 뭔가 에러나서 실패함.
| abcdabckl 이란 문자열이 있다고 하자 이때 i = -1, j = 0 이며, 시작 위치의 상태함수에 들어갈 값은 -1 이다. 1. i와 j를 한칸씩 전진 시킨뒤 비교한다. 2. i와 j가 매치되면 혹은 i == -1 일때 한칸씩 전진한 뒤, j위치에 i를 저장한다. 3. 만약 i와 j가 매치되지 않는다면 i는 상태전이함수에 있는 값으로 전환시킨뒤 2로 돌아간다. 4. j가 n보다 커질때 까지 반복한다. 이 과정을 거친 상태전이함수는 -1 0 0 0 0 1 2 3 0 0 이 된다. |
이 때의 계산횟수는 (n+m) 이다.
// 상태전이함수 생성
void kmp(char *pat) {
int n = strlen(pat);
int i = -1, j = 0;
pi[j] = i;
while(j < n) {
if(i == -1 || (i >= 0 && pat[i] == pat[j])) {
i++;
j++;
pi[j] = i;
}
else i = pi[i];
}
}
// 문자열 비교
void find_pattern(char *arr, char *pat) {
int n = strlen(arr);
int m = strlen(pat);
int i = 0, j = 0;
while(i<n) {
if(j == -1 || (j >= 0 && arr[i] == pat[j])) i++, j++;
if(arr[i] != pat[j]) j = pi[j];
if(j == m) {
printf("The matching %d\n",i-m+1);
j = pi[j];
}
}
}
Rabin–Karp string search algorithm
앞에 설명했던 문자열 알고리즘이, 단순한 문자 자체를 비교하는 알고리즘이었다면, 라빈 카프 알고리즘은 해쉬를 이용하여 해쉬끼리 비교하는 알고리즘이다. 우선 찾으려는 패턴의 해쉬값을 구한다. 그리고 문자열의 앞에서 부터 뒤에서 까지, 해쉬값을 이동시킨다. 이때, mod 연산을 사용하므로 앞에서 26^(m-1)*p mod q 를 뺀 뒤, 그 값에다가 26을 곱하고 다시 mod 연산을 취한뒤, 뒤에 자리를 더한다. 이 경우엔 해쉬충돌이 일어날 가능성이 있으므로 상당히 불안정하고 비효율적이다. 해쉬를 사용하므로 시간 복잡도는 평균적으로 O(n+m) 이다.
