chapter 2-4(String, KMP Algorithm)

문자열

c언어에서 문자열은 char형 배열로 볼 수 있습니다.

특징은 맨 마지막 문자열 \0(NULL)에 의해 종료됩니다.

예를들어 "dog" 라는 char형 3개로 이루어진 문자열을 저장하려면 문자열의 메모리를 4로 두어야합니다.

맨마지막 문자에 \0이 들어가기 때문입니다.

             [0]                          [1]                        [2]                        [3]

d

o

g

\0

---

문자열의 합체 (strcat)

서로 다른 문자열 끼리 합칠 수 있습니다.

보통 strcat 함수를 사용합니다.

예를 들어 char s[20] = "dog", char t[20] = "house"라고 한다면 둘의 문자열을 합치면 "doghouse" 가 됩니다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main() {
	char s[20] = "dog";
	char t[20] = "house";
	strcat(s, t);
	printf("%s", s);
    
	return 0;
}

 strcat(string 1, string 2) 의 의미는 string 1과 string 2의 결합된 문자열이 string 1로 들어간다는 의미입니다.

여기서 주의할점은 char s[20] = "dog"에서 메모리(4) , char t[20] = "house"에서 메모리(6) 을 합쳐서 

최소 char s[]에는 10이상의 메모리 공간이 있어야 합니다. 10미만의 메모리를 가질 시 에는 결합된 문자열이 들어갈 수 

없기 때문입니다.

---

문자열 삽입 (strnins)

문자열 중간에 삽입하는 함수입니다.

char string1[MAX_SIZE] = "amobile";
char* s = string1;

char string2[MAX_SIZE] = "uto";
char* t = string2;

예를 들어 문자열 s = "amobile"   ,   문자열 t ="uto" 일때,  문자열 s에 'a'와 "mobile" 사이 즉, 1번째 위치에 문자열 t를 

삽입하면, 문자열 s 는 "automobile" 이 됩니다.

char *s는 string1의 주소값을 저장하는 포인터 값이고, char *t는 string2의 주소값을 저장하는 포인터 입니다.

void strnins(char* s, char* t, int i) {
	char string[MAX_SIZE];
	char* temp = string;

strnins의 함수입니다.

먼저 string은 문자열 string1과 string2의 문자열의 일부를 저장할 임시 문자열입니다.

string 문자열의 주소값을 저장할 포인터는 temp입니다.

if (i<0 && i>strlen(s)) {
		fprintf(stderr, "Position is out of bounds");
		exit(1);
	}

먼저 변수 i는 문자열 sting1의 i번째 위치에 string2를 삽입하겠다는 의미입니다.

따라서 i가 0보다 작거나 문자열 string1의 문자가 i보다 작으면 삽입할 수 없으므로 프로그램을 종료합니다.

if (!strlen(s))
	strcpy(s, t);
else if (strlen(t)) {
	strncpy(temp, s, i);
	temp[i] = '\0';
	strcat(temp, t);
	strcat(temp, (s + i));
	strcpy(s, temp);
}

첫번째 줄에 if문에서 string1의 문자열의 길이가 0이면 그냥 string2의 문자열을 string1에 복사해줍니다.

삽입할 문자열이 없기 때문입니다.

else if 문에서 문자열 string2의 길이가 0보다 크면 실행해줍니다.

strncpy를 통해 빈 문자열 temp에다가  string1의 0번째 문자부터 i개 문자까지 복사해줍니다.

따라서 i는 1이므로  string1의 0번째 문자부터 i개 문자 즉, 'a' 1개를 빈 문자열 temp에 복사해줍니다.

여기서 주의해야할점이 strncpy는 \0(NULL) 문자까지 복사해주지 않으므로 

문자열 temp에는 달랑 문자 'a' 밖에 들어있지 않습니다.

그러므로 temp[i]번째 에다가 '\0' 문자를 삽입해줍니다.

그 다음 strcat 함수를 통해 temp문자열 뒤에 string2("uto")를 붙여줍니다.

따라서 temp 문자열은 "auto\0 " 가 들어가게 됩니다.

그 다음 strcat 함수를 통해 temp문자열 뒤에 string1의 i번째 문자열부터 끝까지 붙여줍니다.

따라서 string1의 1번째 문자부터 끝까지 ("mobile")을 temp뒤에 붙여줍니다.

결국 temp 문자열은 "automobile\0" 이 됩니다.

마지막으로 temp문자열을 string1에 복사해줍니다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_SIZE 100
void strnins(char* s, char* t, int i);
int main() {
	char string1[MAX_SIZE] = "amobile";
	char* s = string1;
	char string2[MAX_SIZE] = "uto";
	char* t = string2;

	strnins(s, t, 1);
	printf("%s", s);

	return 0;
}
void strnins(char* s, char* t, int i) {
	char string[MAX_SIZE];
	char* temp = string;

	if (i<0 && i>strlen(s)) {
		fprintf(stderr, "Position is out of bounds");
		exit(1);
	}
	if (!strlen(s))
		strcpy(s, t);
	else if (strlen(t)) {
		strncpy(temp, s, i);
		temp[i] = '\0';
		strcat(temp, t);
		strcat(temp, (s + i));
		strcpy(s, temp);
	}
}

---

문자열 매칭 (특정 문자열이 해당 문자열안에 존재하는가)

우리는 흔히 특정 문자열이 해당 문자열안에 있는지 없는지 알고싶을때, 보통은 strstr 함수를 사용합니다.

하지만 strstr 함수는 우리가 사용하는 compiler에서 제대로 작동할지도 미지수고 긴 문자열에서는 오히려 시간복잡도가

너무 크게 나타납니다.

따라서 우리는 우리만의 함수를 구현해야 합니다. 

먼저 기본적인 naive한 방법을 보겠습니다.

int nfind(char * string, char * pat) {
	int i, j;
	int start = 0;
	int lasts = strlen(string) - 1;
	int lastp = strlen(pat) - 1;
	int endmatch = lastp;

해당 문자열 안에 특정 문자열이 몇번째 부터 시작하는지 알려주는 알고리즘입니다.

해당 문자열은 string이고 특정 문자열은 pat입니다.

string = "ababbaabaa" 이고 pat = "aab" 입니다. 따라서 string의 5번째 문자부터 "aab"가 시작하므로 이 함수는 5를 출력합니다.

 변수 start는 string의 첫번째를 가리킵니다.

lasts는 string의 마지막을 가리킵니다.

lastp는 pat의 마지막을 가리킵니다.

endmatch는 pat의 길이만큼 string에서 가리킵니다.

 

 

for (i = 0; endmatch <= lasts; endmatch++, start++) {
		if (string[endmatch] == pat[lastp]) {
			for (j = 0, i = start; j < lastp && string[i] == pat[j]; i++, j++)
				;
				if (j == lastp)return start;
		}
	}
	return -1;
}

for문에서 pat의 마지막 문자와 string[endmatch] 를 비교해서 같으면 두번째 for문으로 들어갑니다.

만약 pat의 마지막 문자와 string[endmatch]의 문자가 같으면 i는 string의 start를 가리키고 j는 pat의 첫번째를 가리킵니다.

두번째 for문에서 문자열이 일치한지 확인하고 j가 lastp까지 도달했다면 문자열이 일치한다는 의미이므로

string의 start를 return해줍니다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_SIZE 100
int nfind(char* string, char* pat);
int main() {
	char string[] = "ababbaabaa";
	char pat[] = "aab";
	printf("%d", nfind(string, pat));

	return 0;
}
int nfind(char * string, char * pat) {
	int i, j;
	int start = 0;
	int lasts = strlen(string) - 1;
	int lastp = strlen(pat) - 1;
	int endmatch = lastp;
	
	for (i = 0; endmatch <= lasts; endmatch++, start++) {
		if (string[endmatch] == pat[lastp]) {
			for (j = 0, i = start; j < lastp && string[i] == pat[j]; i++, j++)
				;
				if (j == lastp)return start;
		}
	}
	return -1;
}

이러한 알고리즘은 가장 좋은 입력이 들어왔을때, ex) string = "aaaa....a", pat = "aaa.....b" 마지막 문자만 비교하기 때문에 이런 경우는 O(N)의 시간복잡도를 가집니다.

하지만 ex) string = "aaaa.....a" , pat = "aaa.......aba" 같은 경우는 마지막 문자가 같으므로 계속 for문으로 비교해주다가 

-1을 return해줍니다. 이럴경우 시간복잡도는 O(N*M)을 갖게됩니다.

---

KMP 알고리즘

방금전에 있는 알고리즘을 좀더 효율적인 알고리즘으로 나타낸게 KMP알고리즘입니다.

먼저 KMP 알고리즘은 찾고자하는 문자열의 접두사와 접미사를 활용하는 방식입니다.

따라서 찾고자하는 문자열의 접두사와 접미사가 일치하는지 안하는지에 대한 정보를 저장할 배열이 필요합니다.

예를들어 "abaabab" 라는 문자열이 있으면 failure 배열에 접두사와 접미사가 같은지 다른지에대한 정보를 저장합니다.

먼저 -1이면 접두사와 접미사가 다른거고 0이면 접두사와 접미사가 1개 같습니다. 1이면 2개 같습니다.

 

 

 

abaabab에서 맨첫글자 a는 글자가 1개밖에 없기 때문에 -1입니다.

abaabab에서 두번째 글자 b는 접두사 a와 같지 않기 때문에 -1입니다.

abaabab에서 세번째 글자 a는 접두사 a와 같기 때문에 0입니다.

abaabab에서 네번째 글자 a는 접두사 a와 같기 때문에 0입니다.

abaabab에서 네번째 글자와 다섯번째 글자 는 접두사 a와 그 다음에 있는 문자 b와 같으므로 1입니다.

abaabab에서 4번째, 5번째, 6번째 글자는 접두사, 그다음 문자, 그다음 문자와 같으므로 2입니다.

abaabab에서 두글자가 같으므로 1입니다.

이를 코드로 구현하면

void fail(char* pat) {
    int i, n = strlen(pat);
    failure[0] = -1;
    for (int j = 1; j < n; j++) {
        i = failure[j - 1];
        while ((pat[j] != pat[i + 1]) && (i >= 0)) //접두사와 접미사가 같지 않고 이전 글자는 같을때
            i = failure[i];
        if (pat[j] == pat[i + 1]) //접두사와 접미사가 서로 같을때
            failure[j] = i + 1;
        else failure[j] = -1; //접두사와 접미사가 서로 다를때
    }
}

변수 n은 "abaabab"의 길이입니다.  변수 i는 접두사의 위치를 가리킵니다.

그 다음 failure[0]은 -1로 초기화 해줍니다.(맨 첫글자는 -1이기 때문에)

변수 j는 접미사의 위치를 가리킵니다.

 

이제 KMP알고리즘을 구현합니다.

int pmatch(char* string, char* pat) {
    int i = 0, j = 0;
    int lens = strlen(string);
    int lenp = strlen(pat);
    fail(pat);
    while (i < lens && j < lenp) {
        if (string[i] == pat[j]) { //string i번째 문자 = pat j번째 문자
            i++;
            j++;
        }
        else if (j == 0) i++; //pat의 위치가 0이면 string의 위치를 한칸 더해 다음 문자와 비교
        else j = failure[j - 1] + 1; //kmp 알고리즘의 핵심
    }
    return ((j == lenp) ? (i - lenp) : -1); //j가 lenp에 도달했으면 문자열을 찾은것이다. 그게 아니면 -1
}

i는 string의 위치를 가리키고 j는 pat의 위치를 가리킵니다.

lens는 string의 길이이고, lenp는 pat의 길이입니다.

fail(pat) 을 통해 pat의 접두사 접미사 정보를 초기화 해줍니다.

이제 while문은 string을 가리키는 위치(i) 와 pat을 가리키는 위치(j)가 각 문자열의 길이를 넘지않으면 실행됩니다.

while안에 if절과 else if 절은 직관적으로 이해가 됩니다.

관건은 else절인데 string의 babcab..... , pattern의 abcac 빨간색 부분까지는 일치하지만 마지막 글자에서 서로 다릅니다.

아까 만든 pattern의 접두사, 접미사 정보를 저장한 failure배열을 통해 다시 문자열을 비교해줄 위치를 

가리켜 줍니다.

string의 babcab... 와 abcac는 다시 비교하는것입니다.

 

 

 

 

 

마지막으로 j가 lenp가 되면 pattern의 문자열이 string에 있다는 의미이므로 (i - lenp)를 return해줍니다.

j가 lenp가 아니면 pattern의 문자열이 string에 없다는 의미이므로 -1을 return해줍니다.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_SIZE 100
#define max_string_size 100
#define max_pattern_size 100
int failure[max_pattern_size];
int pmatch(char* string, char* pat);
void fail(char* pat);
int main() {
    char string[] = "babcabsrjsklabcac";
    char pat[] = "abcac";
    printf("%d", pmatch(string, pat));
 
 
    return 0;
}
int pmatch(char* string, char* pat) {
    int i = 0, j = 0;
    int lens = strlen(string);
    int lenp = strlen(pat);
    fail(pat);
    while (i < lens && j < lenp) {
        if (string[i] == pat[j]) {
            i++;
            j++;
        }
        else if (j == 0) i++;
        else j = failure[j - 1] + 1;
    }
    return ((j == lenp) ? (i - lenp) : -1);
}
void fail(char* pat) {
    int i, n = strlen(pat);
    failure[0] = -1;
    for (int j = 1; j < n; j++) {
        i = failure[j - 1];
        while ((pat[j] != pat[i + 1]) && (i >= 0))
            i = failure[i];
        if (pat[j] == pat[i + 1])
            failure[j] = i + 1;
        else failure[j] = -1;
    }
}

KMP 알고리즘은 O(N+M)의 시간복잡도를 가집니다.