04. 4차시 교육

01.cpp - string.h 함수들 일부 직접 구현하기. <for문>

#include <stdio.h>
 
int strlen(char *str){
    int i;
    for(i=0; str[i]!='\0'; ++i);
    return i;
}
 
void strcpy(char *from, char *to){
    int i;
    for(i=0; from[i]!='\0'; ++i){
        to[i]=from[i];
    }
    to[++i]='\0';
}
 
int strcmp(char *str1, char *str2){
    int i;
    for(i=0; str1[i]!='\0'; ++i){
        if(str1[i]!=str2[i]) return 0;
    }
    ++i;
    if(str1[i]!=str2[i]) return 0;
    else return 1;
}
 
int strchr(char *str, char chr){
    for(int i=0; str[i]!='\0'; ++i){
        if(str[i]==chr) return i;
    }
    return -1;
}
 
int main(){
    char str1[10], str2[10];
    scanf("%s", str1);
    scanf("%s", str2);
    printf("str1 length : %d\n", strlen(str1));
    printf("compare : %d\n", strcmp(str1, str2));
    strcpy(str1, str2);
    printf("str1 copy => str2\nstr1 : %s\nstr2 : %s\n", str1, str2);
    printf("strchr on str1 : 'a' => %d\n", strchr(str1, 'a'));
    return 0;
}

문자열 길이를 비교하는 strlen

from 배열에 있는 값을 to배열으로 복사하는 strcpy

str1과 str2가 같으면 1을, 다르면 0을 반환하는 strcmp

str안에서 chr문자가 있으면 해당 인덱스를, 없으면 -1을 반환하는 strchr.

02.cpp - 1번을 함수 인자를 더 받아서 재귀로 짜기

//recursive call
#include <stdio.h>
 
int strlen(char *str, int n){
    if(str[n]=='\0') return 0;
    return 1+(strlen(str, n+1));
}
 
void strcpy(char *from, char *to, int n){
    if(from[n]=='\0') return;
    to[n]=from[n];
    strcpy(from, to, n+1);
    return;
}
 
int strcmp(char *str1, char *str2, int n){
    if(str1[n]=='\0' && str2[n]=='\0') return 1;
    if(str1[n]!=str2[n]) return 0;
    return strcmp(str1, str2, n+1);
}
 
int strchr(char *str, char chr, int n){
    if(str[n]=='\0') return -1;
    if(str[n]==chr) return n;
    return strchr(str, chr, n+1);
}
 
int main(){
    char str1[10], str2[10];
    scanf("%s", str1);
    scanf("%s", str2);
    printf("str1 length : %d\n", strlen(str1, 0));
    printf("compare : %d\n", strcmp(str1, str2, 0));
    strcpy(str1, str2, 0);
    printf("str1 copy => str2\nstr1 : %s\nstr2 : %s\n", str1, str2);
    printf("strchr on str1 : 'a' => %d\n", strchr(str1, 'a', 0));
    return 0;
}

모든 함수에 int n인자를 추가해서 재귀로 짜보기.

03.cpp - 계단읽기

//https://www.acmicpc.net/problem/10798
 
#include <stdio.h>
char arr[5][16];
char res[100];
int resptr=0;
 
int main(){
    for(int i=0; i<5; ++i){
        scanf("%s", arr[i]);
    }
    for(int i=0; i < 16; ++i){
        for(int j=0; j<5; ++j){
            if(arr[j][i]=='\0'){
                continue;
            }
            res[resptr++]=arr[j][i];
 
        }
    }
    printf("%s", res);
}
 

res[resptr++]은 특정한 규칙이 없거나 불규칙적일때, 배열을 채울 때 씁니다.

04.cpp - Pattern Matching 

<method : Brute-Forcing>

//Pattern matching
 
//test length : N
//Pattern length : M
//Brute-force Big-O : O(NM);
#include <stdio.h>
#include <string.h>
char str[100000];
char pattern[100000];
int p_len;
int main(){
    scanf("%s %s", str, pattern);
    p_len=strlen(pattern);
    for(int i=0; i<strlen(str)-p_len+1; ++i){
        for(int j=0; j<p_len; ++j){
            if(str[i+j]!=pattern[j]) break;
            if(j==p_len-1){
                printf("%d", i);
                return 0;
            }
        }
    }
    return 0;
}

문자열 str 안에서 특정 문자열 pattern을 찾는 문제입니다. 04번 방식은 부르트 포스 방식입니다. 시간은 O(NM)가 걸립니다.

05.cpp - Pattern Matching

<method : Knuth-Morris-Pratt Algorithm>

KMP 알고리즘이란?

Knuth-Morris-Pratt 알고리즘의 줄임말로서 Text 문자열 T에서 Pattern 문자열 P가 부분 문자열로 일치되는 모든 위치를 계산하는 알고리즘입니다.

<첫번째 예시 . 배열은 1부터 시작합니다.>

실패함수 Pi[i] : 접두사와 접미사가 같아지는 최대 길이

단, Pi[i] < i

abbbacabbba 일 때 i=11, Pi[i]=5

aaaaaaaaaa 일 때 i=10l, Pi[i]=9;

* 접두사와 접미사가 같다?

배열에서 앞에 n개와 뒤의 n개가 똑같으면 접두사와 접미사가 같은겁니다.

ex) 배열 a a b a a 가 있다고 합시다.

접두사==접미사인 부분을 모두 골라보면

1) a // a

2)aa // aa

최대 => 2

ex) 배열 a a b a a b a 가 있다고 합시다.

접두사==접미사인 부분을 모두 골라보면

1) a // a

2) aaba // aaba

최대 => 4

이 Pi[i]를 이용해서 뭘 할 수 있을까요?

다른 문자가 나왔다구요? 그렇다면 Pi[i]에서 구했던 길이 만큼 슉~ 땡겨와서

여기서부터 다시 검사를 시작하면 되겠죠~(시간 단축!)

자 그럼 그림을 통해서 어떻게 Pi[i]를 만드는지 볼까요?

노란점 i 번째 위치에서의 Pi값을 계산한다고 할 때, (Pi값은 접두사와 접미사가 같아지는 최대의 길이)

우선 Pi[j]는 위의 그림에서 두 박스 부분이 같아지는 최대의 길이를 말하죠. 빨간색 점과 노란색 점을 포함하기 전에 미리 이전의 연산에서 구해놓은 값입니다.

접미사는 (오른쪽 박스의) 시작점에서 시작해서 i-1번째까지 이고, 이게 접두사와 같습니다.

여기서 만약 빨간색 점과 노란색 점 부분의 값이 같다면, 이제 Pi[i-1+1], 즉, Pi[i]는 이전 Pi값인 Pi[i-1]에 1을 더한 값과 같습니다.

만약 같지 않다면 Pi[Pi[j]]+1의 값과 i값을 비교합니다.

이 값이 같다면 노란색 부분이 Pi[i]입니다. 이 값이 다르면, 바로 윗문장을 다시 합니다.

<두번째 예시 . 배열이 0부터 시작합니다.>

위의 예제만으론 이해가 아직 안되었을거에요. 이번엔 하나씩하나씩 해보죠.

자. 처음 상태입니다. j는 0번째에, i는 1번째에 있어요.

여기서 P[0]과 P[1]이 문자 a로 같으니 Pi[j]+1을 Pi[i]에 집어 넣어 줍시다.

그럼 이 상태가 되죠.

여기서 P[1]과 P[2]가 다르므로 j를 그 이전의 인덱스인 j-1로 이동하고 이곳의 값인 Pi[j-1]을 인덱스로 갖는 곳으로 이동합니다. 그곳에서 값을 비교해서 같이 않으면 반복, (0이면 그냥 0 반환), 같으면 그자리에서의 Pi값에 +1한 값을 Pi[i]에 넣어줍니다. 이 내용은 Pi[8]에서 자세히 나옵니다. 그때 가서 보도록 하죠.

<아래는 현재 상태입니다.>

여기서 P[j]와 P[i]가 같으므로 Pi[i]에 Pi[i-1]+1을(==i에서 바로 이전의 Pi값.) 집어넣어줍니다. i++. j++.

여기도 P[j]와 P[i]가 같으므로 Pi[i]에 Pi[i-1]+1을(==i에서 바로 이전의 Pi값에 +1) 집어넣어줍니다. i++. j++.

여기도 P[j]와 P[i]가 같으므로 Pi[i]에 Pi[i-1]+1을(==i에서 바로 이전의 Pi값.) 집어넣어줍니다. i++. j++.

여기도 P[j]와 P[i]가 같으므로 Pi[i]에 Pi[i-1]+1을(==i에서 바로 이전의 Pi값.) 집어넣어줍니다. i++. j++.

여기도 P[j]와 P[i]가 같으므로 Pi[i]에 Pi[i-1]+1을(==i에서 바로 이전의 Pi값.) 집어넣어줍니다. i++. j++.

이제 P[j]와 P[i]가 같지 않습니다. j는 바로 전 인덱스의 값을 Pi의 인덱스로 가지는 곳, 즉 Pi[2]로 갑니다. (여기서 j는 2입니다.)

여기서 P[j]와 P[i]가 같지 않으므로 j를 다시 Pi[Pi[j-1]]으로 만듭니다. 여기서 P[j] == P[i] 가 됩니다. (여기서 j는 1입니다.) 이제 Pi[i]는 Pi[j]에 1을 더한 수, 즉 2가 되겠죠.

<아래는 설명입니다.>

결국, 다음과 같이 Pi가 만들어집니다.

Pi부분만 구현한 코드는 다음과 같습니다. 

다음 차시에선 이것을 어떻게 이용하는지를 알아보겠습니다.

#include <stdio.h>
#include <string.h>
char Pattern[100000]="aabaabaaa";
int PI[100000];
int m;
int i, j;
void Make_pi(){//pi정의.
    m=strlen(Pattern);//PI는 Pattern과 수가 같답니다.
    PI[0]=0;//무조건 0
    j=0;
    for(int i=1; i<m; ++i){
        while(j>0 && Pattern[j]!=Pattern[i]){
            j=PI[j-1];
        }
        if(Pattern[j]==Pattern[i])
            j++;
        PI[i]=j;
    }
 
}
 
int  main(){
    Make_pi();
    printf("\ni : %d, j : %d\n", i, j);
    for(int n=0; n<m; ++n){
        printf("%d ", PI[n]);
    }
    printf("\n\n");
}

아래는 코드 실행 결과입니다.

잘 구현이 된 것을 볼 수 있습니다.