2-5강 - Multidimensional Arrays, Strings (다차원 배열, 문자열)

6. Representation of Multidimensional Arrays

1) 기본

1> 선언

a[upper_0][upper_1] ... [upper_n-1]

2> 원소의 개수

upper_0 * upper_1 * ... * upper_n-1

 

2) two common ways to representation multidimensional arrays

row major order : stores multidimensional arrays by rows
column major order : stores multidimensional arrays by columns

1> row major order

- a[upper_0][upper_1]

• a의 각 행(upper_0)은 upper_1개의 element를 가진다.
• a[i][j]의 address = a + i*upper_1 + j

- a[upper_0][upper_1][upper_2]

•  upper_1Xupper_2 shape의 2-d array를 upper_0개 가지는 형태
•  a[i][j][k]의 address = a + i*upper_1*upper_2 + j*upper_2 + k

2> addressing formula

a[upper_0][upper_1] ... [upper_n-1]

- a[i_0][i_1] ... [i_n-1]의 address 

 

---

 

7. Strings

1) ADT

1> object : a finite sequence of zero or more characters

0개 이상 문자의 finite 연속

2> functions 

- String Null(m) : 최대 길이가 m으로 확보한 채 NULL string("") return

- int Compare(s, t) : (사전식 순서에 따라 맨 앞 글자부터) s가 크면 -1, 같으면 0, t가 크면 1

- bool IsNull(s) :

• if (Compare(s, NULL)) return false <s가 NULL -> Compare(s, NULL) == 0  -> false return>
• else return true <s가 NULL이 아니면 -> Compare(s, NULL) 1 or -1 return -> true return>
• (Compare(s, NULL)==0 ? false : true)

 

- int Length(s) : Compare(s, NULL)로 NULL인지 확인하고 아니면 s의 길이 출력 

• if (Compare(s, NULL)) return s 길이 <s != NULL-> 조건식 == 1 or -1 -> s 길이 return>
• else return 0 <s == NULL -> 조건식 == 0 -> 0 return>

- String Concat(s, t) : Compare(t, NULL)로 NULL인지 확인 -> NULL 아니면 s와 t 합쳐 return / NULL이면 s

• if (Compare(t, NULL)) return s와 t 합친 문자열 <t != NULL -> 조건식 == 1 or -1 -> ... >
• else retrun s <t == NULL -> 조건식 == 0 -> s return>

- String Substr(s, i, j)

: j가 양수이고 i+j-1가 s의 길이보다 작으면 s의 i번째~i+j-1번째까지의 substring을 return 그 이외는 NULL

• if ((j>0) && (i+j-1)<Length(s)) return s의 i~i+j-1 index 사이의 substing return
• else return NULL

2) String in C

1> representation

character array의 마지막을 null character로 끝낸다.

2> 선언

char s[100] = "dog";

char s[] = "dog"; -> 이 경우 그 뒤에 추가적인 공간을 확보할 수 없는 단점이 있다.

3> string pointer 만들기

#include <string.h>
#define MAX_SIZE 100

char string1[MAX_SIZE], *s = string1;
char string2[MAX_SIZE], *t = string2;

4> C언어는 <string.h>에 여러 문자열 내장함수가 있다.

https://ajaelee.tistory.com/15

5> 문자열 삽입하는 함수 예시 (string insertion)

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 101 /*maximum number of terms 1*/


void strnins(char *s, char *t, int i)
{/*insert string t into string s at position i */
	char string[MAX_SIZE], *temp = string;
	if (i<0 && i > strlen(s)) {
		fprint(stderr, "Position is out of bounds");
		exit(1);
	}
	if (!strlen(s)) strcpy(s, t); // s가 비어있다면 t를 그냥 s에 복사하면 된다.
	else if (strlen(t)) { // s가 존재하며 t도 존재하는 경우에는
		strncpy(temp, s, i); // s의 i번째까지를 temp에 복사
		strcat(temp, t); // temp와 t를 concat
		strcat(temp, (s + i)); // temp와 s의 i번째 이후를 concat // s+i는 address 표현
		strcpy(s, temp); // temp를 s에 복사
	}
}

 

3) Pattern Matching

탐색하는 문자열을 'string' / 탐색 중인 패턴을 'pat'으로 지칭하겠습니다.

1> strstr 함수 (strstr(string, pat))

- ('pat' 내부에 'string'이 없는 경우) null pointer return

- ('pat' 내부에 'string'이 있는 경우) string 내부에 pat이 시작되는 pointer return

※ 다른 방법도 있다.

2> 기본적인 방법

- 'string'의 앞 글자부터 pattern이 있는지 차례대로 확인

- 'pat'이 'string' 내부에 없을 경우 O(m*n)의 시간복잡도

3> 기본 방법에 대한 개선

- 탐색 중에 'pat'의 길이가 남은 문자보다 길이가 길 때 탐색 멈춘다.

- 남은 문자를 확인하기 전에 'pat'의 첫 글자와 마지막 글자를 확인

4> 예제 1 : 마지막 index를 먼저 확인하는 방식

- [0] 용어 정의

• lasts : string의 마지막 문자 index (lastp : pat의 마지막 문자 index
• start ~ endmatch : string 내부에서 탐색하는 부분
• i : string에서 일치여부 확인하는 원소 index (j : pat에서 일치여부 확인하는 원소 index)

- [1] 초기화 (초기 설정)

• lasts는 string의 길이에서 1을 뺀 값 (lastp는 pat의 길이에서 1을 뺀 값)
• string 내부 탐색 부분 : 맨 앞부터 pat의 길이만큼 탐색하므로 start에는 0, endmatch에는 lastp 

- [2] 첫 번째 loop :  string 내부 탐색 부분을 한 칸씩 옆으로 이동 (탐색 부분이 string 끝에 도착할 때까지)

• 탐색 부분의 마지막(string[endmatch])과 pat의 마지막(pat[lastp])이 같은지 확인
• 같다면 두 번째 loop (탐색 부분의 맨 앞(string[i=start]), pat의 맨 앞(pat[j=0])부터 하나씩 같은지 확인)
• 다르면 첫 번째 loop 계속 진행(탐색 부분을 한 칸씩 오른쪽으로 이동)

- [3] 두 번째 loop

• 일치 여부 확인 (i와 j를 준비)
• 탐색 부분의 맨 앞과 pat의 맨 앞을 index로 설정 (i = start / j = 0)
• 조건 : 일치 여부 확인(string[i] == pat[j])은 lastp까지 (j < lastp)
• 일치한다면 i와 j를 증가시키면서 위의 조건 계속 확인

- [4] loop 종료 후에는 j와 lastp가 같은 상황이므로 현재 탐색 부분의 맨 앞 index를 return

int nfind(char* string, char* pat)
{
	/* match the last character of the pattern first, and then match from the beginning */
	int i; // string의 탐색 index
	int j; // pat의 탐색 index
	int lasts = strlen(string) - 1;
	int lastp = strlen(pat) - 1;
	int start = 0; // 탐색 중인 pattern(탐색 부분)의 시작 index
	int endmatch = lastp; // 탐색 중인 pattern(탐색 부분)의 끝 index
	for (i = 0; endmatch <= lasts; endmatch++, start++) // 탐색 부분을 한 칸씩 올린다.
	{
		if (string[endmatch] == pat[lastp]) // pattern의 끝과 탐색 부분의 끝이 일치할 경우
			for (j = 0, i = start; j < lastp && string[i] == pat[j]; i++,j++)
				; // pat은 맨 앞부터, string은 탐색 부분의 맨 앞부터 일치하는지 확인
		if (j == lastp) return start; // 그래서 j가 pat의 마지막 까지 도달(성공)하는지 확인 /* successful*/
	}
	return -1;
}

 

cf> KMP 알고리즘

접두사와 접미사의 개념을 이용해서 '반복되는 연산을 얼마나 줄일 수 있는지' 판별하여 확인할 문자열을 빠르게 점프

 

1) fail 함수

void fail(char *pat)

1> 정의 : failure array를 완성한다.

- failure[i] : pat[0] ~ pat[i] 사이에 접두사와 접미사가 최대로 일치하는 길이 - 1

2> 구현

- [0] 용어 정의

• n : pat의 길이이자 failure의 길이
• j : 조사 중인 index
• i : failure[j-1] 혹은 failure[j]의 값 저장 (i + 1 : 접두사 접미사가 일치한 길이)

- [1] 초기화 (초기 설정)

• failure의 0번째 에는 -1을 대입
• n에는 pat의 길이를 대입

- [2] 첫 번째 loop : failure의 1번째 index 부터 n-1번째 index까지 차례로 값을 할당

• i에는 이전에 설정한 failure 값 할당 (i = failure[j-1])
• 두 번째 loop : (접두사, 접미사를 한 칸씩 증가해서 일치하는지 확인) 아래 두 조건 만족시 다음 글자도 조건 만족 => 이전 접두사의 길이-1을 i에 할당 (=> 추후에 i+1<접미사가 일치한 길이>를 failure에 할당)
  • 1} 이전에 일치한 글자가 있는지 (i>=0)
  • 2} 현재 확인 중인 pat의 글자(pat[j])와 이번에 확인할 pat의 접두사 마지막 글자(pat[i+1])가 다른지 
• 두 번째 loop의 결과 (loop 만족 == 접두사, 접미사가 연속으로 일치)
  • loop을 만족하면 failure[j]에 i+1<접미사가 일치한 길이>를 할당
  • loop을 만족하지 못하면 -1을 할당

#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100

int failure[MAX_SIZE];
char str1[MAX_SIZE];
char str2[MAX_SIZE];

void fail(char *pat)
{
	int n = strlen(pat); // pat의 길이이자 failure의 길이
	int i; // failure[j-1] 혹은 failure[j]의 값
	// i + 1 : 접미사, 접두사가 일치한 길이
	// failure[j] = 0~j까지 접미사 , 접두사가 일치한 길이 - 1
	failure[0] = -1; // failure 0번째에는 -1을 대입
	for (int j = 1; j < n; j++){ // failure의 1번째부터 n-1번째까지 차례로 값을 할당
		i = failure[j - 1]; // 이전에 설정한 failure 값 저장
		while ((pat[j] != pat[i + 1]) && (i >= 0))
			// 1> i가 0이상 == 이전에 접두사, 접미사가 1개 이상 일치
			// 2> 현재 확인 중인 pat의 글자와 이번에 확인할 접두사 글자가 같은지
			i = failure[i]; // 그렇다면 이전까지 일치한 접두사의 길이-1 을 할당 (추후에 i+1을 할
		if (pat[j] == pat[i + 1])
			failure[j] = i + 1; // 위 while문 만족시 현재 접두사, 접미사가 일치한 길이-1 을 할당
		else failure[j] = -1;
	}
}

2) KMP 구현

int pmatch(char *string, char *pat)

2> 구현

- [0] 용어 정의

• i : string의 탐색 중인 index / j : pat의 탐색 중인 index
• lens : string의 길이 / lenp : pat의 길이

- [1] 초기화

• i와 j는 맨 앞의 값으로 초기화 (0) / lens와 lenp는 strlen을 이용해서 초기화

- [2] 첫 번째 loop : i 혹은 j가 끝에 도착할 때까지 반복 

• string을 탐색 중인 원소(string[i])와 pat을 탐색 중인 원소(pat[j])가 같다면 각각 다음 칸으로 이동
• (string[i] != pat[j]이고) pat이 맨 앞이라면(직전 과정에서 중복 부분 없었다.) string만 다음 칸으로 이동 (i++)
• (string[i] != pat[j]이고) pat이 맨 앞이 아니면(직전 과정에서 중복 부분 있음) j를 접두사 일치 마지막 부분으로 이동

- [3] return : (j가 끝까지 도달했느냐에 따라 return 값 변경)

• j가 끝까지 도달했다 == string 안에서 pat 발견 => string 내부에서 pattern이 시작되는 index(i-lenp) return
• j가 끝까지 도달 못 함 == i가 끝까지 도달 == string이 끝까지 탐색할 동안 pat을 발견 못한 => -1 return

int pmatch(char *string, char *pat)
{
/* Knuth, Morris, Pratt string matching algorithm*/
	int i = 0; // string의 탐색 중인 index
	int j = 0; // pat의 탐색 중인 index
	int lens = strlen(string);
	int lenp = strlen(pat);
	while(i < lens && j < lenp){
		if (string[i] == pat[j]) {
			// string에서 탐색 중인 원소와 pat을 탐색 중인 원소가 같다면
			// 각각 다음 칸으로 이동
			i++;
			j++;
		}
		// string에서 탐색 중인 원소와 pat을 탐색 중인 원소가 다르고
		else if (j == 0) // pat이 맨 앞이다 == 직전 과정에서 접두사, 접미사 중복부분 없었다.
			i++; // string만 한 칸 이동 (점프 안 한 경우)
		else  // pat이 맨 앞이 아니다 == 직전 과정에서 접두사, 접미사 중복 부분 있었다.
			j = failure[j - 1] + 1; // j를 일치하는 접두사의 마지막 부분으로 이동 
			// 위 과정이 점프인 이유 : 원래 j를 맨 앞부터 점검해야 하는데 접두사 부분은 중복되므로 접두사 마지막 부분부터 확인
	}
	return ((j == lenp) ? (i - lenp) : -1);
}