SMALL
KMP 알고리즘이란?
- KMP 알고리즘은 문자열 검색 알고리즘 중 하나로, 문자열에서 특정 패턴을 찾는데 사용됩니다. KMP 알고리즘은 문자열 내에서 특정 패턴이 나타나는 위치를 찾을 때, 일반적으로 사용되는 브루트 포스 알고리즘보다 훨씬 빠르게 동작합니다.
KMP 알고리즘의 원리
- KMP 알고리즘의 핵심 아이디어는, 일치하지 않는 문자열 부분을 다시 검색하지 않고 이전 검색 결과를 활용하여 패턴을 찾아가는 것입니다. 이를 위해 패턴 문자열의 접두사와 접미사에 대한 정보를 미리 계산해두고, 이를 이용하여 문자열을 검색합니다.
KMP 알고리즘
- C언어
#include <stdio.h>
#include <string.h>
void computeLPSArray(char* pattern, int M, int* lps);
void KMPSearch(char* text, char* pattern)
{
int M = strlen(pattern);
int N = strlen(text);
int lps[M];
computeLPSArray(pattern, M, lps);
int i = 0, j = 0;
while (i < N) {
if (pattern[j] == text[i]) {
j++;
i++;
}
if (j == M) {
printf("Pattern found at index %d\n", i - j);
j = lps[j - 1];
}
else if (i < N && pattern[j] != text[i]) {
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
}
void computeLPSArray(char* pattern, int M, int* lps)
{
int len = 0;
int i = 1;
lps[0] = 0;
while (i < M) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
}
else {
if (len != 0) {
len = lps[len - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
}- C#
using System;
class GFG {
void KMPSearch(string pat, string txt)
{
int M = pat.Length;
int N = txt.Length;
int[] lps = new int[M];
int j = 0;
computeLPSArray(pat, M, lps);
int i = 0;
while (i < N) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M) {
Console.Write("Found pattern "
+ "at index " + (i - j));
j = lps[j - 1];
}
// mismatch after j matches
else if (i < N && pat[j] != txt[i]) {
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
void computeLPSArray(string pat, int M, int[] lps)
{
int len = 0;
int i = 1;
lps[0] = 0;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0) {
len = lps[len - 1];
}
else
{
lps[i] = len;
i++;
}
}
}
}
public static void Main()
{
string txt = "ABABDABACDABABCABAB";
string pat = "ABABCABAB";
new GFG().KMPSearch(pat, txt);
}
}- 파이썬
def kmp(text, pattern):
n = len(text)
m = len(pattern)
lps = compute_lps(pattern)
i, j = 0, 0
while i < n:
if text[i] == pattern[j]:
i += 1
j += 1
if j == m:
return i - j
elif i < n and text[i] != pattern[j]:
if j != 0:
j = lps[j-1]
else:
i += 1
return -1
def compute_lps(pattern):
m = len(pattern)
lps = [0] * m
length = 0
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length-1]
else:
lps[i] = 0
i += 1
return lps
예제 문제
LIST
'공부 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 넓이 우선 탐색(BFS) (0) | 2023.03.05 |
|---|---|
| [알고리즘] 깊이 우선 탐색(DFS) (0) | 2023.03.05 |
| [알고리즘] 에라토스테네스의 체 (0) | 2023.02.02 |
