KMP

KMP 문자열 매칭
구현하기 쉬운 문자열 매칭 알고리즘
단순 비교 문자열 매칭
문자열 처음부터 끝까지 계속 비교하는 알고리즘
단순 비교 문자열 매칭 알고리즘은 O(NM)의 시간 복잡도를 가짐
#include<stdio.h>
#include<string.h>
char *parent="ABCDEFG";
char *patter="EF";
int main(void){
int parentSize=strlen(parent);
int patternSize=strlen(patter);
for(int i=0;i<=parentSize-patterSize; i++){
int fount=1;
for(int j=0;j<patternSize;j++){
if(parent[i+j]!=pattern[j]){found=0; break; }
}
if(found){
printf("%d번째에서 찾았습니다.\n", i+1);
}
}
system("pause");
return 0;
}
KMP 문자열 매칭
KMP 문자열 매칭 알고리즘을 활용하면, O(N+M)의 시간 복잡도로 문제를 해결할 수 있다.

KMP 문자열 매칭은 접두사와 접미사를 활용해 빠르게 문자열 매칭을 수행하는 알고리즘이다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *parent ="acabacdabac";
char *pattern="abacdab";
int* maketable(char* patter){
int patternSize=strlen(pattern);
int* table=(int*)malloc(sizeof(int)*patternSize);
for(int i=0;i<patternSize;i++){
table[i]=0;
}
int j=0;
for(int i=1;i<patternSize;i++){
while(j>0 && pattern[i]!=pattern[j]){
j=table[j-1];
}
if(pattern[i]==pattern[j]){
table[i]=++j;
}
}
return table;
}
void KMP(char* parent, char* pattern){
int* table=maketable(pattern);
int parentSize=strlen(parent);
int patternSize=strlen(pattern);
int j=0;
for(int i=0;i<parentSize;i++){
while(j>0 && parent[i]!=pattern[j]){
j=table[j-1];
}
if(parent[i]==pattern[j]){
if(j==patternSize-1){
printf("[인덱스 %d]에서 매칭 성공\n", i-patternSize+2);
j=table[j];
}
else{
j++;
}
}
}
}
int main(void){
KMP(parent, pattern);
system("pause");
return 0;
}
KMP 문자열 매칭 알고리즘은 O(N+M)의 시간 복잡도를 가진다.