Chapter 2. ARRAYS AND STRUCTURES

지환·2022년 4월 3일
DS - Horowitz
0

2.1 ARRAYS

2.1.1 The Abstract Data Type

Array를 ADT로 봐보자. (p.52)
array object를 정의하고, function으론 (1)creation (2)retrieve, (3)store 세가지가 있다.

대부분 프로그래머는 array를 "연속적인 memory location set"으로 본다.
하지만 이는 구현에 집중한 것이지, 대부분 그렇게 구현되긴하지만, 항상 그런건 아니다.
ADT 보면 알겠지만,
Array는 "a consecutive set of memory location"보단 더 general한 개념이다.

2.1.2 Arrays in C

int list1[5];와 int *list2는 확실히 다르다.
list1과 list2 모두 int를 가리키긴 하지만, 전자는 int 5개의 공간을 예약해둔 것이고, 후자는 그냥 int형 type의 주소를 저장한다.

포인터에 정수를 더하면 해당 type에 맞게 덧셈이 된다.
int*에 1을 더하면 int type byte만큼 더해지고,
char*에 1을 더하면 char type byte만큼 더해진다.

2.2 DYNAMICALLY ALLOCATED ARRAYS

2.2.1 ONE-DIMENSIONAL ARRAYS

보통 MACRO를 통해 배열 길이를 정한다.
그렇게 고정된 길이는 문제가 될 수 있어서, malloc함수(or chapter 1에서 만든MALLOC macro)를 이용하여 array를 선언할 수 있다.

2.2.2 TWO-DIMENSIONAL ARRAYS

2차원 배열은, 각 element가 1차원 배열인 1차원 배열이다.

int x[3][5];
length가 3인 1차원 배열 x를 선언한 것이다.
그리고 이 배열 x의 각 원소는 length가 5인 1차원 배열이다.

C는 x[i][j]를 찾을때 우선, x[i]를 통해 해당 row의 첫번째 주소값을 먼저 얻는다.(여기서 얻는 주소값은 x[i]의 주소값이 아니다. x[i][0]의 주소값이다.)
그 다음 [j]로 접근하는 것이다.(해당 주솟값(x[i])에 j*sizeof(int) 더해서 접근)

Dynamically create a two-dimensional array

//row와 col 입력하면 row×col인 2차원 배열 만들어서 반환

int **make2dArray(int rows, int cols) {
	int **x, i;
    
    MALLOC(x, rows * sizeof(*x))  //macro
    
    for(i = 0; i < rows; i++)
    	MALLOC(x[i], cols * sizeof(**x))
    
    return x;
}

2차원 배열을 dynamically allocate 하려면
위에서 말했듯이, 2차원 배열은 그냥 element가 좀 특별한 1차원 배열이다.
그러니까 1차원 배열을 먼저 할당해주고, 그 1차원 배열의 elements에 다시 1차원 배열을 할당해주면 된다.
(p.56 그림 참고, 이 그림이 이차원 배열을 제일 잘 나타내주는 듯)

그냥 막무가내로 rows×cols만큼 allocate 해버리면 2차원 배열이 제대로 작동 안한다.
물론 rows*cols만큼의 공간을 memory에 쭉 할당해야되는건 맞는데 그전에 해야될게 있다.
a[x][y]는 결국 a[x]라는 주소값(&a[x][0])에 y만큼 더하는 연산을 하는 것이므로
우리는 a[x]가 a[x][0]를 가리키도록 할 필요가 있어서 a[x]를 위한 공간을 먼저 할당한다.
(이렇게 안보일 수도 있지만) 얘도 그냥 2차원 배열 선언하는 것처럼 memory에 쭉 할당된다.
a[0], a[1], ...이 각 열의 시작을 가리키기 위한 추가작업을 한 것 뿐이다.
그냥 2차원 배열도 a[0], a[1], ...이 각 열의 시작주소를 가리킨다. 원리를 잘 알고있자.

malloc외에 calloc과 realloc도 있다.
calloc은 모든 bits를 0으로 초기화하고(따라서 초기화된 배열 선언할때 쓰임),
realloc은 사이즈를 조정한다.
둘 다 MALLOC macro 처럼 macro로 선언해서 유효한지 판별하고 사용하면 좋다.

2.3 STRUCTRUES AND UNIONS

2.3.1 Structures

K.N.K에서 봤듯이, structure가 제공하는 operation은 (1)assignment와 (2)member selection 밖에 없다.
(예전 C들은 assignment도 잘 인정안한다고 하니 하나하나 넘기는게 assign하는게 나을듯)

따라서 == 같은 비교연산은 잘 작동하지 않기 때문에(holes 때문에), 비교를 하고 싶으면 멤버 하나하나 체크하는 함수를 따로 만들어서 써라.

2.3.2 Unions

PASS

2.3.3 Internal Implementation Of Structures

structure의 member는 memory에 순서대로 저장된다.
(각 요소가 memory 내에 잘 배열되도록.. holes이나 padding이 중간중간에 올 수 있다.)
size는 knk에서 말한대로 특정 byte수의 배수

2.3.4 Self-Referential Structures

linked list 얘기. PASS

2.4 POLYNOMIALS

2.4.1 The Abstract Data Type

Array 자체로 data structure이지만, 이를 이용해 다른 ADT를 구현할 수 있다.
list도 array로 구현할 수 있는데, delete 같은 기능을 구현하는게 제한돼서 linked list를 주로 사용한다.

Polynomial을 array로 구현해보자.
우선 object와 functions를 기술한 ADT는 p.67에 있다.

2.4.2 Polynomial Representation

#define MAX_DEGREE 101

typedef struct {
	int degree;
    float coef[MAX_DEGREE];
} polynomial;

ploynomail a; 같은 식으로 선언해서 descending order로 coef를 넣고, degree엔 최고차항 차수를 넣는다.
하지만 이렇게 하면 다항식 마다 배열을 할당해주는거라 공간 낭비가 너무 심하다.(대부분 MAX_DEGREE만큼 항이 필요하진 않으니)

그래서 하나의 global array인 term을 선언해서 여기에 모든 polynomial을 저장한다.

#define MAX_TERMS 100

typedef struct {
	float coef;
    int expon;
} polynomial;

polynomial terms[MAX_TERMS];
int avail = 0;

이렇게 전체 배열을 선언해두고, A 다항식과 B 다항식을 terms에 저장했다고하면,
start A는 A 시작점을, finish A는 A 끝점 index를 나타낸다.
B도 마찬가지다.
avail은 사용가능한, 즉 가장 끝 다항식의 다음 element index를 나타낸다.예시 그림

여기서 specification과 representation의 차이가 생긴다.
ADT에선 그냥 poly로 했지만, 실제로 쓰려면 (startA, finishA) 조합으로 나타나진다.

하지만 항의 계수가 모두 0이 아니라면, 후자 방식이 전자 방식보다 공간을 2배나 차지한다. 그래도 대부분은 후자 방식이 더 낫다.

2.4.3 Polynomial Addition

term 배열의 뒤에 앞의 두 다항식을 더한 덧셈 결과를 저장한다.(배열 길이 초과시 error print)

padd 함수

//padd 함수

void padd(int startA, int finishA, int startB, int finishB, int *startD, int *finishD)
{
	*startD = avail;
    
    while(startA <= finishA && startB <= finishB) {
    	switch(COMPARE(term[startA].expon, term[startB].expon)) {
    		case -1:    //A expon < B expon
        		attach(term[startB].coef, term[startB].expon);
            	startB++;
            	break;
        	case 0:     //A expon == B expon
        		if (term[startA].coef + term[startB].coef) {
            		attach(term[startA].coef + term[startB].coef, term[startA].expon);
                	startA++;
                	startB++;
            	}
            	break;
        	case 1:     //A expon > B expon
        		attach(term[startA].coef, term[startA].expon);
            	startA++;
        	    break;
		}
    }
    
    //아래는 남은 항들 붙이는거
    for(; startA <= finishA; startA++;)
    	attach(term[startA].coef, term[startA].expon);
        
    for(; startB <= finishB; startB++;)
    	attach(term[startB].coef, term[startB].expon);
        
    *finishD = avail - 1;
}
//attach 함수

void attach(float coef, int expon) {
	if (avail >= MAX_TERMS) {
    	fprintf(stderr, "Too many terms in polynomial\n");
        exit(EXIT_FAILURE);
    }
    term[avail].coef = coef;
    term[avail].expon = expon;
	avail++;
}

Analysis (padd)
처음 loop는 최악의 경우, 즉 두 다항식이 일치하는 차수가 하나도 없는 경우, n+m번 반복문을 수행한다.(A의 항 개수:n, B의 항 개수:m)
아래 loop도 최대 n번, m번씩 수행하므로 이 algorithm의 asymtotic notation은 O(n+m)이다.

attach에서 배열 꽉찼다고 무조건 종료하기보단,
필요없는 다항식을 제거하고 기존 데이터를 옮겨서 끝에 공간을 만드는 것도 좋은 방법이다.
대신 이러면 데이터를 이동해야될 수 있어서 시간이 좀 걸린다.

2.5 SPARCE MATRICES

2.5.1 The Abstract Data Type

matrix를 적을때 보통 m×n식으로 적는다. 그럼 m은 row이고, n은 column이다.

2차원 배열로 간단하게 저장할 수 있겠지만, data가 드물게 있는(대부분이 0) matrix(sparce matrix)를 그렇게 저장하면 공간이 낭비된다.

자세한 representation 정의하기전에 ADT 먼저 정의해보면.. p.74
(함수는 create, transpose, add, multiply)

2.5.2 Sparce Matrix Representation

<rows, cols, value> 형태의 triple로 행렬 값을 나타낼 수 있다.
이 triple의 배열을 만들어서 sparce matrix를 저장한다.

transpose 연산의 편리를 위해 row는 ascending order로 작성하고,
같은 row내에서 col도 ascending order로 작성한다.
또 operation이 끝났다는걸 확실히 하기위해 각 rows와 columns의 개수와 nonzero elements의 개수도 명시한다.

implementation

#define MAX_TERMS 101

typedef struct {
	int col;
    int row;
    int value;
} term;

term a[MAX_TERMS];

a[1]부터 matrix의 triple 데이터를 저장하고,
a[0]에는 col개수/row개수/nonzero-value개수를 저장한다.

2.5.3 Transposing A Matrix

전치행렬(나무위키)

matrix를 무작정 transpose해버리면 원래의 row ascending order가 무너진다.
(유지하려고 해도 데이터를 이동시켜야되고,, 일이 많다)
따라서 column을 기준으로 순서대로 transpose해야한다.
col 0을 row 0으로 transpose, col 1을 row 1로 transpose, ...
(원래 row가 잘 정렬돼있어서 이렇게 변환한 matrix의 col도 잘 정렬된다.)

Transpose 함수

//transpose 함수

void transpose(term a[], term b[]) {
	int currentb = 1;  //b의 index 따라가는 변수

	b[0].row = a[0].row;
    b[0].col = a[0].col;
    b[0].value = a[0].value;
    
    if (n > 0)    //nonzero matrix
    	for (int i = 1; i <= a[0].col; i++) {
    		for (int j = 1; j <= a[0].value; j++) {
            	if (a[j].col == i) {
                	b[currentb].row = a[j].col;
                    b[currentb].col = a[j].row;
                    b[currentb].value = a[j].value;
                    cureentb++;
                }
    	}
}

Analysis (transpose)
for loop 두개 제외하곤 constant time이니까 저 두개만 고려.
따라서 O(columns * elements) 이다.

2차원 배열로 표현해서 하면 O(columns * rows)이다.
elements = columns * rows 이므로, 더 빠르다.
즉 우리는 공간을 절약하고 시간을 좀 더 쓴것이다.

fast transpose 함수

위 함수보다 공간을 좀 더 쓰고 더 빠르게 수행할 수 있다.
1. 각 column 별 elements 개수를 구한다.(이는 변환된 matrix의 각 row별 elements의 개수이다.)
2. 1번 정보를 통해 각 row의 starting point를 알 수 있다.
3. 이 정보를 활용해 변환 matrix에 하나하나 옮긴다.

//fast transpose 함수

void fastTranspose(term a[], term b[]) {
	int rowTerms[MAX_COL], startingPos[MAX_COL];
    int i;

	b[0].row = a[0].col;
    b[0].col = a[0].row;
    b[0].value = a[0].value;
    
    if (a[0].value > 0) {     //nonzero matrix
    	for (i = 0; i < a[0].col; i++)
        	rowTerms[i] = 0;  //rowTerms 초기화
            
        for (i = 1; i < a[0].value; i++)
        	rowTerms[a[i].col]++;  //각 column별 elemnts 개수 저장
        
        //변환될 matrix의 각 row의 starting position 구하기
        //이전 starting position + 이전 row의 elements 개수
        startingPos[0] = 1;
        for (i = 1; i < a[0].col; i++)
        	startingPos[i] = startingPos[i-1] + rowTerms[i-1];
            
        for (i = 1; i <= a[0].value; i++) {
        	b[startingPos[a[i].col]].row = a[i].row;
            b[startingPos[a[i].col]].col = a[i].col;
            b[startingPos[a[i].col]].value = a[i].value;
            startingPos[a[i].col]++;    //저장했으니, starting position update
        }
    }
}

Analysis (fast transpose)
O(columns + elements)이다.
elements = rows * columns일때 O(comlumns * rows)이므로 이는 이차원배열 표현법에서의 transpose와 같다고 볼 수 있다.
하지만 우리는 array보다 공간을 절약할 수 있다.

2.5.4 Matrix Multiplication

행렬곱(나무위키)

행렬 A와 B의 곱 D를 구해보자.
근데 B의 column을 하나하나 찾기 힘드니, transpose 시키면 columns이 정렬되는 점을 이용하자.

mmult 함수

void mmult(term a[], term b[], term d[]) {
	int sum = 0;
    int row = a[1].row;
    int column;
    
    int totalA = a[0].value;
    int totalB = b[0].value;
    int totalD = 0;
    
    //1열2행 값 계산하고 1열3행 값 계산하려면 열을 다시 처음부터 곱해야된다. 이를 위한 rowBegin
    int rowBegin = 1;
    
    if (a[0].col != b[0].row) {
    	fprintf(stderr, "Incompatible matrices\n");
        exit(EXIT_FAILURE);
    }
    
	term newB[MAX_TERMS];    
    fastTranspose(b, newB);
    
    //set boundary condition
    a[totalA+1].row = a[0].row;
    newB[totalB+1].row = newB[0].row;
    newB[totalB+1].col = 0;
    //이 조건들은 아래 반복문이 돌면서 마지막 부분까지 성공적으로 돌려면 필요하다.
    //반복문 조건 복잡하게 만드는 것보다 이렇게 좀 유도리 있게하는게 덜 복잡하네
    
    for (int i = 1; i <= totalA;) {
    	column = newB[1].row;
    	for (int j = 1; j <= totalB + 1;) {
        	if (a[i].row != row) { //특정 열에 대해 한번 모두 진행된 경우
            	storeSum(d, &totalD, row, column, &sum);
                i = rowBegin; //row를 다시 처음으로 되돌림(같은 열, 다음 행에 대해 진행하기위해)
                for (; newB[j].row == column; j++) ;  //남은 column skip
                column = newB[j].row;
            }
            else if (newB[j].row != column) { //특정 행에 대해 한번 모두 진행한 경우
            	storeSum(d, &totalD, row, column, &sum);
                i = rowBegin;
                column = newB[j].row;
            }
        	else {
	        	switch(COMPARE(a[i].col, newB[j].col)) { //이 둘이 같아야 곱한다
    	        	case -1:
        	        	i++; break;  //일치하는게 없다 == 반대쪽이 0이다.
            	    case 0:
                		sum += (a[i].value * newB[j].value);
                    	i++; j++;
                    	break;
                	case 1:
                		j++; break;
            	}
            }
        }
        //한 row에 대해 끝, 이제 다음 row로 가기위해 rowBegin, row 값 변경
        for (; a[i].row == row; i++) ;
        rowBegin = i;
        row = a[i].row;
    }
    
    d[0].row = a[0].row;
    d[0].col = b[0].col;
    d[0].value = totalD;
}
void storeSum(term d[], int *totalD, int row, int column, int *sum) {
	if (*sum)
    	if (*totalD < MAX_TERMS) {
        	d[++*totalD].row = row;
            d[totalD].col = column;
            d[totalD].value = *sum;
            *sum = 0;
        }
    }
    else {
    	fprintf(stderr, "Numbers of terms exceeds %d", MAX_TERMS);
        exit(EXIT_FAILURE);
    }
}

Analysis (mmult)
반복문 시작 전 fastTranspose에 O(colsB + totalB) 만큼 필요하다.

이 아래론 솔직히 책 내용이 전부다 명확하게 이해가 안돼서 일단 내가 이해한대로 적어봐야지.(나중에 다시 보자..)

outer loop나 inner loop나 for (int i=0; i<m; i++); 같은 명확한(?) 반복문이 아니여서 반복횟수가 totalA*(totalB+1)이라고 바로 말하진 못한다.
(만약 for (int i=0; i<m; i+=2);라면 얘의 반복횟수는 m이 아니라 m/2이다.)

그래서 안쪽부터보면.. 결국 i or j or both 가 안쪽 loop가 한번돌때마다 1씩 증가한다.

현재 row의 항의 개수를 termsRow라고 해보자.
i는 한 row를 진행할때 최대 termsRow * colsB 만큼 증가할 수 있다.
(왜냐하면 한 column 진행하고 나면 reset되는데 그게 최대 colsB번 될 수 있으니까)
(termsRow가 colsA 아닌가? : ㅇㅇ 아님. termsRow는 실제 값이 있는 항의 개수)

j는 최대 totalB + 1만큼 증가할 수 있다.

그 둘 중 하나만(or) 끝까지 가면 한 row가 끝나는 것이므로 둘을 더해버리면,
안쪽 첫번째 loop의 시간은 O(colsB*termsRow + totalB)이다.
안쪽 두번째 loop의 시간은 O(termsRow)이다.

이 두 loop가 모두 돌면 바깥 loop가 한번 돈 것이다.
이는 O(colsB*termsRow + totalB)이다.
바깥 loop를 한번 돌았다는건 한 row를 진행했단 뜻이다.
따라서 전체 시간은 (모든 row에 대해 계산하면)
O(∑row(colsB×termsRow+totalB))=O(colsB×totalA+rowsA×totalB)O(\displaystyle\sum_{row}(colsB \times termsRow + totalB)) =O(colsB\times totalA + rowsA\times totalB)
(위 풀이 과정은 여기)

따라서 O(colsB*totalA + rowsA*totalB)이다.

matrix를 2차원 배열로 나타낸 경우와도 비교해보자.(코드는 간단하니까 궁금하면 p.83참고)
반복문이 3개가 중첩돼서 O(rowsA * colsB * colsA)이다.

rowsA*colsA >= totalA 이고, rowsB*colsB >= totalB 이므로,
mmult 또한 O(rowsA * colsB * colsA)이다.

worst case인 경우 rowsA*colsA == totalA, rowsB*colsB == totalB 이므로,
이때는 mmult가 2차원 배열 표현법보다 느리다.
하지만 sparse matrix라면 mmult 성능이 훨씬 좋다.

2.6 REPRESENTATION OF MULTIDIMENSIONAL ARRAYS

C에선 기본적으로 array of array 방식으로 2차원 배열을 나타낸다.
이 방식 말고도 그냥 1차원 배열처럼 memory에 쭉 저장하는 방법이 있는데, 이는 mapping이 쉽지않다.

row major order일때..
2차원 배열 a[upper0][upper1]으로 선언됐다면,
a[i][j]의 adress는 다음과 같다.
α\alpha + i*upper1 + j
(α\alpha는 a[0][0]의 adress라고 가정)
(type은 주소계산할때 알아서 되니까 고려안함)

3차원 배열 a[upper0][upper1][upper2]으로 선언됐다면,
a[i][j][k]의 adress는 다음과 같다.
α\alpha + i*upper1*upper2 + j*upper2 + k

(일반화 한 식이 궁금하면 p.86)

2.7 STRINGS

2.7.1 Abstract Data Type

String의 ADT는 p.88

2.7.2 Strings in C

다양한 standard string 함수들 있고.. 얘네 조합해서 우리만의 함수를 만들 수도 있다.
(만들때 time이나 space complexity 잘 생각하기)

2.7.3 Pattern Matching

string에서 pat pettern을 찾는 함수를 만들어 보자.
(물론 strstr 함수가 있긴하지만, 구현 방법은 다양하다.)

제일 쉽지만 비효율 적인 방법은 하나씩 비교하며 pattern을 찾는 것이다.
pat이 string에 없다면 O(n*m)이 걸린다.(n은 pat길이, m은 string길이)

첫과 끝이 같은지 확인하며, 남은 문자열이 pat 보다 짧다면 그만둔다. 이렇게 시간을 더 단축시킬 수 있다.

위 방법대로 만든 함수 nfind는 p.93

analysis (nfind)
string = "aa...a"이고 pat = "a...ab"라면 O(m)이 된다.
하지만 평균적인 시간은 단축되지만 여전히 worst case에선 O(m*n)이다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

Knuth, Morris, Pratt은 linear complexity를 가지는 이런 pattern matching algorithm을 개발했다.
Failure Function이다.(KMP alrgorithm)

pattern이 matching되다가 실패하면 그 정보를 바탕으로 다시 matching을 시작하는 것이다.
"abcab" 패턴과 "ab??~" string의 매칭에서 3번째에서 틀렸다면
그 세번째와 패턴 첫번째를 다시 비교하면 된다.
하지만 "abcab" 패턴과 "abca??~" string의 매칭에서 4번째에서 틀렸다면
string의 4번째와 패턴의 두번째를 비교해나가면 된다.

Failure Function (KMP algorithm)

Definition
: If p=p0p1p2...p(n-1) is a pattern, then the failure function, f, is defined as
f(j) = p0p1...pi = p(j-i)p(j-i+1)...pj를 만족하는 i가 존재할때 가장 큰 i값(0<=i<j),
없다면 -1

쉽게 말하자면, pattern에 접두사와 접미사가 일치하는 최대 길이(자기자신 제외)를 작성해 주는 것이다.
(접두사와 접미사가 일치해야 당연히 그게 실패했을때 다시 일치하는 접두사는 제끼고 시작할 수 있다. 일치하는 부분이 중간에 있을수도있지않나? 라고 생각할 수 있는데 좀만 생각해보면 중간부터 일치하는 부분이 있으면 그곳까지 싹다 접미사로 계산되기때문에 상관없다, 접미사로 계산 안된거면 중간부터 일치하다가 끝부분에 실패한 것일거고..)

쉽게 이해하기
즉, 뒤에서부터 n개의 접미사가 앞에서부터 n개의 접두사와 일치할 경우, 해당 접미사의 끝 위치는 n-1(index 생각해서..)을 실패함수 값으로 가진다. 그 n-1 index까지 접두사에서 일치하므로 접미사 다음에서 dismatch되면 n index부터 다시 보면 된다.
(접미사는 구간별로 나누며 판단한다. 즉, pat의 길이를 처음부터 1, 2, 3, ..., k 까지 자르면서 해당 구간에서 접두사와 접미사가 얼마나 일치하는지 판단한다.)

ex)

j0123456789
patabcabcacab
f-1-1-10123-101

이렇게 실패함수를 계산해두고 pattern P와 string S가 matching을 하다가 실패한다면,
(실패 위치는 PjP_j와 SiS_i라고 해보면,)
Pf(j−1)+1P_{f(j-1)+1}와 SiS_i 부터 다시 매칭하기 시작하면 된다.
j=0j=0이라면, P0P_0와 Si+1S_{i+1}을 다시 매칭하면 된다.

예를들어, 위에서 j가 7일때 dismatch가 발생하면, P4P_4인 b와 SiS_i를 매칭해보면 된다.

j가 4,5,6 이여도 불필요하게 또 비교하긴하네.
(j가 4일때 P_1과 S_i를 비교해봤자 어차피 dismatch가 났으니까 둘은 다르다.)
위보다 더 효율적으로되긴 했지만 저 부분도 해결한 알고리즘이 있을라나

pmatch 함수

failure 함수를 이용한 pattern matching 함수

기본은 string과 pattern이 일치하면 쭉쭉 진행되는거다.
근데 dismatch가 나면 경우에 따라 다르게 처리해야한다.
1) pattern의 처음부터 dismatch가 난 경우: 그냥 i만 증가시킨다.
2) pattern의 중간에서 dismatch가 난 경우: 실패함수에 의해 pattern의 앞부분과 일치할 수 있으니 j만 수정해준다.

int pmatch(char *string, char *pat) {
	int i = 0, j = 0;
    int lens = strlen(string);
    int lenp = strlen(pat);
    
    while (i < lens && j < lenp) {
    	if (string[i] == pat[j]) {
        	i++; j++;
        }
        else if (j == 0)  //matching이 안되다가 mismatch가 나면 i만 +1 해준다.
        	i++;
        else  //matching이 되다가 mismatch가 난 경우 j를 실패함수값 활용해 다시 세팅
        	j = failure[j-1]+1;  //실패함수 값들을 array에 모두 구해놓는다.
    }
    return ( (j == lenp) ? (i - lenp) : -1 );
}

Analysis (pmatch)
while 문은 둘 중 하나가 끝까지 가면 끝난다.
i는 감소하지 않고 1씩 증가만 하므로, m = strlen(string)보다 많이 실행될 수 없다.
j는 실패함수에 의해 감소하기도하는데, 이는 j++보다 많이 실행될 수 없다.(0인 경우엔 감소 안함, j++로 증가를 해야 감소한다.)
근데 j++는 i++가 증가할때 같이 증가하므로 j++는 m보다 많이 실행될 수 없다.
따라서 모든 statement가 m보다 많이 실행될 수 없으므로, O(m) = O(strlen(string))이다.

Failure 함수

f(j)={−1:if,  j = 0fm(j−1)+1:m은 Pfk(j−1)+1=Pj 를 만족하는 최솟값 k−1:if,  만족하는 k가 없을 경우f(j) = \begin{cases}-1:\quad if,\; j\ =\ 0\\ f^m(j-1)+1:\quad m은\ P_{f^k(j-1)+1}=P_j\ 를\ 만족하는\ 최솟값\ k\\ -1:\quad if,\; 만족하는\ k가\ 없을\ 경우 \end{cases}

쉽게 생각하면, k가 1일때를 먼저 보자.
f(j−1)+1f(j-1)+1은 j 이전 character의 실패함수 값 + 1이다.
즉, 뒤의 조건을 같이 보면 "이전 character의 실패함수 값 위치 다음 character"와 "j 위치 character"가 같으면 이전 character 실패함수 값에 더하기 1을 해준다는 것이다.
다시말해, 접두사와 접미사가 같은 길이가 더 늘어나는 것이므로 당연히 +1을 해주면 된다.

k가 1이 아닌 경우는? 왜 합성함수를 썼을까?
해당 구간(0~j)까지 봤을때 접두사 접미사가 가장 길게 일치하는 지점을 찾아야된다.
0~j구간에서 실패했을때, 즉, j-1 위치의 실패함수 값의 위치로 가서 그 다음과 j를 비교했을때 실패했을때 바로 -1로 해버리면 안된다.
더 작은 접두사와 접미사가 일치할 수 있기 때문이다.
j-1의 실패함수 값을 i라고 해보자. (f(j-1) = i)
P[i+1]과 P[j]가 일치하지 않으면, 0~i+1 구간은 접두사가 될 수 없지만, 0~i까진 (j-i-1)~(j-1)과 일치한단 소리다.(i > 0)
따라서 그 다음 j까지 포함했을때의 접미사와 일치하는 가장 긴 접두사를 찾으려면 0~i 구간을 찾아봐야한다.
j까지 포함했을때 접미사와 일치할 가능성이 있는 곳은 f(i)+1이다.(0~i와 (j-i-1)~(j-1)이 끝부분이 같으니까)
그래서 다시 P[f(i)+1]와 P[j]를 비교해보는 것이다.
그래서 합성함수 조건이 있는 것이고, k는 최솟값이라는 조건이 있는 것이다.(최솟값이여야 접두사 접미사 최대길이로 구할테니)

위 함수 식을 그대로 구현하면 다음과 같다.

void fail(char *pat) {
	int i;
	int 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  //i<0 이면
        	failure[j] = -1;
}
처음엔 [0]에 -1 넣어두고 시작.
j=1부터 시작해서 f(j)+1 위치의 character와 비교하며 같으면 +1 한 값을 넣어줌
다르면 좀 더 찾아보고(합성함수), 끝까지(== i가 -1이 될때까지) 다르면 -1
(i가 -1이고 같을 수도 있는데, 그 경우는 if문에 의해 같이 처리된다.)

즉 한번더 정리하면,
위 while문은 접두접미가 같아서 멈추거나, i가 0보다 작아져서 멈추거나 둘 중 하나이거나,
처음이랑 현재 구간 마지막이 같아서 멈춘 경우 이렇게 세가지로 나눌 수 있다.
그리고 그 세가지 경우를 아래 if-else문으로 분류해 값을 처리한다.(마지막 경우는 if문에 포함됨)

for문은 n-1번 실행된다.
그 안에 while문은 i를 decrease 시킨다.
i가 증가하는 곳은 if문 뿐인데, 이는 n-1 이상 실행될 수 없으므로 while문을 통한 감소 또한 n-1 이상 실행될 수 없다.
즉, while문이 최대로 실행되도 n-1번이다.
((n-1) * (n-1)이 아니다. 왜냐하면 for문 내부의 모든(while포함) statement가 n-1번 이하로 실행되니까)
따라서 time complexity는 O(n) = O(strlen(pat))이다.

종합하면,
처음으로 이 함수를 실행해서 failure function 값을 얻고,
pattern matching 함수를 실행하는데
O(strlen(pat) + strlen(string))만큼 걸린다.

2.8 REFERENCES AND SELECTED READINGS

SIAM Journal on Computing, 6:2, 1977, pp.323-350

Introduction to Algorithms Second Edition

profile
지환
이전 포스트

Chapter 1. BACIS CONCEPTS

다음 포스트

Chapter 3. STACKS AND QUEUES

0개의 댓글