KMP랑 BM 너무 어렵다. 나중에 꼭 다시봐야한다..
책에서 쉽게 설명해주는데도 이해하기가 힘들다.
연습문제 Q_1 > 널 문자 다음에 문자를 대입해도 정말 출력되지 않는지 확인하세요.
#include <stdio.h>
int main() {
char st[10];
st[0] = 'A';
st[1] = 'B';
st[2] = 'C';
st[3] = 'D';
st[4] = '\0'; // 문자열의 끝을 인식시켜줌. 문자열의 형태가 아닌 문자를 하나씩 넣어줬으므로 문자열의 형태를 갖기 위해선 널문자를 추가해주는것이 안전.
st[5] = 'X'; // 문자열의 끝 이후이므로 읽히지 않음.
printf("문자열 st에는 \"%s\"가 들어 있습니다.", st);
}
출력결과 : ABCD
연습문제 Q_2 > 실습 8 - 5 에서 포인터를 교환하는 함수를 실습 2 - 7에서 만든 함수 형식 매크로 swap와 같은 방법으로 바꾸어보세요.
함수 매크로 정의는 함수와는 다르게 그대로 대체되므로 call by value / call by reference에 대한 고민이 필요없음.
#define swap(type, x, y) do{ type t = x; x = y; y = t }
//사용 = > swap((char *), x, y)
연습문제 Q_3 > 포인터 x, y가 가리키는 문자열의 내용을 모두 바꾸어 넣는 함수를 작성하세요.
내 코드
배열 크기가 각자 달라서, 짧은 문자열을 긴 문자열의 배열에 넣으면 나머지 부분은 NULL로 채운다.
#include <stdio.h>
void swap_str(char *x, char *y) { // 배열 메모리 공간에 문자열이 저장되어 있기 때문에 참조해서 수정 가능.
char a;
// 둘 중 더 짧은 문자열의 끝이 올 때 까지 교환.
while(*x!='\0' && *y!='\0') {
a = *x; *x = *y; *y = a;
x++; y++;
}
// x가 참조하고 있는 배열의 문자열이 더 짧을 경우( x 길이 < y 길이 )
if(*x=='\0') {
while(*y!='\0') // y의 남은 문자열 부분을 모두 null문자로 채워줌.
*y++='\0';
}
// y가 참조하고 있는 배열의 문자열이 더 짧을 경우 ( x 길이 > y 길이 )
if(*y=='\0') {
while(*x!='\0') // x의 남은 문자열 부분을 모두 null문자로 채워줌.
*x++='\0';
}
}
int main() {
char s1[] = "ABCD"; // 배열 메모리에 문자열을 저장했으므로 수정가능.
char s2[] = "EFHGD"; // 배열 메모리에 문자열을 저장했으므로 수정가능.
printf("%s\n", s1);
printf("%s\n", s2);
swap_str(s1, s2);
printf("%s\n", s1);
printf("%s\n", s2);
}정답 제공 코드
배열을 미리 넉넉하게 선언해놓고, 범위안에서 문자열이 다 교환되도록 작성.
/* Q3 두 문자열의 내용을 바꾸기 */
#include <stdio.h>
/*--- 두 문자열 x, y를 교환합니다. ---*/
void swap_str(char *x, char *y)
{
char *temp;
while (*x && *y) { /* 짧은 문자열의 끝까지 문자열을 교환 */
char t = *x; *x++ = *y; *y++ = t;
}
if (*x) { /* x가 더 긴 문자열이라면 */
temp = x;
while (*x) { *y++ = *x++; } /* x의 나머지를 y로 복사 */
*temp = *y = '\0'; // ABCD - A 일 때, 둘을 교환하고 B 부분을 NULL로 채우는 것.
}
else if (*y) { /* y가 더 긴 문자열이라면 */
temp = y;
while (*y) { *x++ = *y++; } /* y의 나머지를 x로 복사 */
*temp = *x = '\0'; // ABCD - A 일 때, 둘을 교환하고 B 부분을 NULL로 채우는 것.
}
else {
*x = *y = '\0';
}
}
int main(void)
{
char s1[128], s2[128];
//문자열 단위들은 뒤에 널문자가 자연히 들어가는 사실은 scanf에서 받을 때도 마찬가지.
printf("문자열 S1 :"); scanf("%s", s1);
printf("문자열 S2 :"); scanf("%s", s2);
swap_str(s1, s2);
printf("두 문자열을 교환했습니다.\n");
printf("문자열 S1 : %s\n", s1);
printf("문자열 S2 : %s\n", s2);
return 0;
}
연습문제 Q_4 > 실습 8 - 6, 실습 8 - 7, 실습 8- 8 의 str_len 함수를 strlen 함수처럼 동작하는 함수로 수정하세요. 또 수정한 함수들을 서로 비교해 보세요.
#include <stdio.h>
// 실습 8 - 6 기반
size_t str_len1(const char *s) {
int len = 0;
while(s[len]) {
len++;
}
return len;
}
// 실습 8 - 7 기반
size_t str_len2(const char *s) {
int len = 0;
while(*s++)
len++;
return len;
}
// 실습 8 - 8 기반
size_t str_len3(const char *s) {
char *p = s;
while(*s)
s++;
return s - p; // 주솟값 차이로 길이 계산.
}
int main() {
char str[256];
printf("문자열 : ");
scanf("%s", str);
printf("이 문자열의 길이는 %d입니다.\n", str_len3(str));
return 0;
}
연습문제 Q_5 > 실습 8-9의 str_chr 함수를 strchr 함수와 같은 동작을 할 수 있게 수정하세요.
// 실습 8-9 랑 완전히 같지않은, 내가 짠 코드 기반임.
#include <stdio.h>
char *str_chr(const char *s, int c) {
while(*s!='\0') {
if(*s == c)
return s;
s++;
}
return NULL;
}
int main() {
char str[64]; // 이 문자열에서 검색
char tmp[64];
int ch; // 검색할 문자
char *idx;
printf("문자열 : ");
scanf("%s", str);
printf("검색할 문자 : ");
scanf("%s", tmp); // 먼저 문자열로 검색할 문자를 읽어 들입니다.
ch = tmp[0]; // 첫 번째 문자를 검색 문자로 지정
if((idx = str_chr(str, ch)) == NULL)
printf("문자 '%c'은(는) 문자열에 없습니다.\n", ch);
else
printf("문자 '%c'은(는) %d번째에 있습니다.\n", ch, idx - str + 1);
return 0;
}
연습문제 Q_6 > strrchr 함수와 같은 동작을 할 수 있게 str_rchr 함수를 작성하세요.
char *str_rchr(const char *s, int c);
#include <stdio.h>
// 참고로 초기의 C언어는 함수로 전달하는 매개변수로 char 형이나 short 형 등의 값을 먼저 int 형으로 형 변환을 했기 때문에 표준 라이브러리 함수에서 '문자'를 주고받을 때는 char 형이 아니라 int 형으로 주고받는다. 게다가 어차피 비교연산같은걸 할 때에도 int형보다 작은 자료형은 int 형으로 바뀌면서 계산되므로 미리 이렇게 쓰는게 현명한 방식이였다고 생각함.
char *str_rchr(const char *s, int c) {
int i = 0;
// strlen과 같은 역할의 while문
while(s[i]!='\0')
i++;
// i 는 현재 s의 length
for(i = i - 1; i >= 0; i--) {
if(s[i]==c)
return &s[i];
}
return NULL;
}
int main() {
char str[64];
char tmp[64];
int ch;
char *idx;
printf("문자열 : ");
scanf("%s", str);
printf("검색할 문자 : ");
scanf("%s", tmp);
ch = tmp[0];
if((idx = str_rchr(str, ch)) == NULL)
printf("문자 '%c'은(는) 문자열에 없습니다.\n", ch);
else
printf("문자 '%c'은(는) %d번쨰에 있습니다.\n", ch ,idx - str + 1);
}
//정답제공코드 : 널문자를 만날 때 까지 앞에서부터 계속해서 검사하고, 값을 찾을 때마다 새로 업데이트. 내 코드 효율이 더 좋다고 생각한다.
//char *str_rchr(const char *s, int c)
//{
// const char *p = NULL;
//
// c = (char)c;
// while (1) {
// if (*s == c)
// p = s;
// if (*s == '\0')
// break;
// s++;
// }
// return (char *)p;
//}
연습문제 Q_7 > strncmp 함수와 같은 동작을 하는 함수 str_ncmp를 작성하세요.
int str_ncmp(const char *s1, const char *s2, size_t n);
#include <stdio.h>
int str_ncmp(const char *s1, const char *s2, size_t n) {
while(*s1 == *s2 && (*s1!='\0' && *s2!='\0')) { // 널 문자 이후는 비교하지 않음.
n--;
if(n == 0) // 비교 갯수만큼 모두 같다면
return 0;
s1++;
s2++;
}
return *s1 - *s2; // 문자 코드값 차이만큼 리턴
}
int main() {
char st[128];
int sz;
puts("\"ABCD\"와 비교합니다.");
puts("\"XXXX\"면 종료합니다.");
while(1) {
printf("문자열 st : ");
scanf("%s", st);
printf("비교할 갯수 : ");
scanf("%d", &sz);
if(str_ncmp("XXXX", st, sz) == 0)
break;
printf("str_ncmp(\"ABCD\", st, sz) = %d\n", str_ncmp("ABCD", st, sz));
}
return 0;
}
//정답제공 : 길이에 대한 차는 +-1로 표시해주는 방식이고, 코드가 간결함.
//#include <stdio.h>
//#include <string.h>
//
//int str_ncmp(const char *s1, const char *s2, size_t n)
//{
// while (n && *s1 && *s2) {
// if (*s1 != *s2)
// return (unsigned char)*s1 - (unsigned char)*s2;
// s1++;
// s2++;
// n--;
// }
// if (!n) return 0; // n == 0으로 반복문이 끝났을 때
// if (*s1) return 1; // *s2=='\0'으로 반복문이 끝났을 때(길이에 대한 차이는 +-1로 해줌)
// return -1; // *s1 == '\0'으로 반복문이 끝났을 때(길이에 대한 차이는 +-1로 해줌)
//}
//
연습문제 Q_8 > 알파벳 대문자 / 소문자를 구분하지 않고 두 문자열을 비교하는 함수를 작성하세요.
#include <stdio.h>
#include <stdlib.h>
// 동일판단에 대소문자가 상관없음. 대신 다를 경우의 리턴값 a - b와 a - B 값의 두 값은 다름.
// 나는 두 값의 차이가 32라면 같은문자라고 판단하는 형태를 취했기 때문인데, 만약 처음부터 두 값중 대문자인 값(어떤 값 이하)을 알게 될 경우 +32해서 결국엔 소문자끼리 비교시키게끔 통일시킨다면, 다를 경우의 리턴값을 통일시킬수있음.
int str_cmpic(const char *s1, const char *s2) {
while(abs(*s1-*s2) == 32||*s1 == *s2) { // 대문자와 소문자의 차이는 32.
if(*s1 == '\0')
return 0;
s1++;
s2++;
}
return *s1 - *s2;
}
// 동일판단에 대소문자가 상관없음. 대신 다를 경우의 리턴값 a - b와 a - B 값의 두 값은 다름.
// 나는 두 값의 차이가 32라면 같은문자라고 판단하는 형태를 취했기 때문인데, 만약 처음부터 두 값중 대문자인 값(어떤 값 이하)을 알게 될 경우 +32해서 결국엔 소문자끼리 비교시키게끔 통일시킨다면, 다를 경우의 리턴값을 통일시킬수있음.
int str_ncmpic(const char *s1, const char *s2, size_t n) {
while((abs(*s1-*s2)==32||*s1 == *s2) && (*s1!='\0' && *s2!='\0')) { // 널 문자 이후는 비교하지 않음.
n--;
if(n == 0) // 비교 갯수만큼 모두 같다면
return 0;
s1++;
s2++;
}
return *s1 - *s2; // 문자 코드값 차이만큼 리턴.
}
int main() {
char st[128];
int sz;
puts("\"ABCD\"와 비교합니다.");
puts("\"XXXX\"면 종료합니다.");
while(1) {
printf("문자열 st : ");
scanf("%s", st);
printf("비교할 갯수 : ");
scanf("%d", &sz);
if(str_ncmpic("XXXX", st, sz) == 0)
break;
printf("str_ncmpic(\"ABCD\", st, sz) = %d\n", str_ncmpic("ABCD", st, sz));
}
return 0;
}
//정답제공 : 아예 toupper함수를 씀. 그로 인해 위에서 내 것처럼 a - B a - b의 차이값이 다르지 않음.
//#include <ctype.h>
//#include <stdio.h>
//#include <string.h>
//
//int str_cmpic(const char *s1, const char *s2)
//{
// while (toupper(*s1) == toupper(*s2)) {
// if (*s1 == '\0')
// return 0;
// s1++;
// s2++;
// }
// return (unsigned char)toupper(*s1) - (unsigned char)toupper(*s2);
//}
//
//int str_ncmpic(const char *s1, const char *s2, size_t n)
//{
// while (n && *s1 && *s2) {
// if (toupper(*s1) != toupper(*s2))
// return (unsigned char)toupper(*s1) - (unsigned char)toupper(*s2);
// s1++;
// s2++;
// n--;
// }
// if (!n) return 0;
// if (*s1) return toupper(*s1);
// return toupper(*s2);
//}
연습문제 Q_9 > 오른쪽처럼 브루트 - 포스법의 검색 과정을 자세히 출력하는 프로그램을 작성하세요. 패턴을 옮길 때마다 검사하는 텍스트의 첫 번째 문자 인덱스를 출력하고 검사 과정에서 비교하는 두 문자가 일치하면 +, 다르면 |를 출력하세요. 마지막에는 비교한 횟수를 출력하세요.
#include <stdio.h>
int bf_match(const char txt[], const char pat[]) {
int pt = 0; // txt 커서
int pp = 0; // pat 커서
int counter = 0;
while(txt[pt] != '\0' && pat[pp] != '\0') {
if(pp == 0)
printf("%2d ", counter++);
else
printf("%*s", 3, " ");
printf("%s\n", txt);
printf("%*s", 3 + pt, " ");
if(txt[pt] == pat[pp]) {
pt++;
pp++;
putchar('+');
} else {
// 텍스트의 위치를 한칸 이동시키고(= 이 패스에서 처음 검사했던 문자 다음 위치부터 검사), 패턴은 처음부터 검사.
pt = pt - pp + 1; // 현재 텍스트의 위치 + 1
pp = 0; // 맨앞자리
putchar('|');
}
putchar('\n');
printf("%*s%s\n", 3 + counter - 1, " ", pat); //패스의 counter 만큼 띄워줘야하는데, counter를 이미 한번 증가시킨 상태이므로 - 1해준 값을 넣어줌. 또는 3 + pt - pp 해도 됨.
}
if(pat[pp] == '\0') // 패턴검사가 끝나서 반복문이 종료되었을 경우 = 찾음
return pt - pp;
return -1;
}
int main() {
int idx;
char s1[256]; // 텍스트
char s2[256]; // 패턴
puts("브루트 포스법");
printf("텍스트 : ");
scanf("%s", s1);
printf("패턴 : ");
scanf("%s", s2);
idx = bf_match(s1, s2);
if(idx == -1)
puts("텍스트에 패턴이 없습니다.");
else
printf("%d번째 문자부터 match합니다.\n", idx + 1);
return 0;
}
연습문제 Q_10 > bf_match 함수는 텍스트에 패턴이 여러 개 있으면 가장 앞쪽의 인덱스를 반환합니다. 이제는 가장 뒤쪽의 인덱스를 반환하는 bf_matchr함수를 작성해 보세요.
#include <stdio.h>
#include <string.h>
int bf_match(const char txt[], const char pat[]) {
int pt = 0; // txt 커서
int pp = 0; // pat 커서
int pp_last = 0;
// 아래 while 문과 strlen의 동작방식은 같다. 결과도 당연히 같다. 길이는 이렇게 널문자를 대상으로찾는과정이기에, 함수 매개변수가 현재 배열인데, 포인터여도 아래 while문 strlen문 둘다 잘 동작한다. 하지만 sizeof는 당연히 다른거고.
while(txt[pt] != '\0')
pt++;
while(pat[pp] != '\0')
pp++;
// pt = strlen(txt);
// pp = strlen(pat);
pp_last = pp - 1; // pat의 끝자리
//시작은 각 문자열의 널문자부터인데 딱히 상관없을듯.
while(pt >= 0 && pp >= 0) {
if(txt[pt] == pat[pp]) {
pt--;
pp--;
} else {
pt = pt + pp_last - 1;
pp = pp_last;
}
}
if(pp == -1)
return pt + 1; // 마지막으로 pt-- 작업을 했으므로 하나 증가해줘야해
return -1;
}
int main() {
int idx;
char s1[256]; // 텍스트
char s2[256]; // 패턴
puts("브루트 포스법");
printf("텍스트 : ");
scanf("%s", s1);
printf("패턴 : ");
scanf("%s", s2);
idx = bf_match(s1, s2);
if(idx == -1)
puts("텍스트에 패턴이 없습니다.");
else
printf("%d번째 문자부터 match합니다.\n", idx + 1);
return 0;
}
//제공된 정답. 방식이 조금 다르고, 코드가 훨씬 이해하기 쉽고 간결하다.
//int bf_matchr(const char txt[], const char pat[])
//{
// int txt_len = strlen(txt);
// int pat_len = strlen(pat);
// int pt = txt_len - pat_len; 만약 길이 10 vs 5라면, 인덱스 5부터 시작하여 딱 들어맞음.
// int pp;
//
//
// while (pt >= 0) {
// pp = 0;
// while (txt[pt] == pat[pp]) {
// if (pp == pat_len - 1)
// return pt - pp;
// pp++;
// pt++;
// }
// pt = pt - pp - 1; 시작자리 - 1
// }
//
// return -1;
//}
연습문제 Q_11 > Q9와 마찬가지로 KMP법을 사용해 검색 과정을 출력하는 프로그램을 작성하세요.
#include <stdio.h>
int kmp_match(const char txt[], const char pat[]) {
int pt = 1; // txt 커서
int pp = 0; // pat 커서
int skip[1024]; // 건너뛰기 표
int counter=0;
int tmp;
// 표 만들기 시작
skip[pt] = 0; // 인덱스 1부터 시작이며, 맨 앞은 검사하지않고도 바로 0으로 초기화해줌. ( 한칸 미루고 겹치기 전 )
while(pat[pt] != '\0') {
if(pat[pt] == pat[pp])
skip[++pt] = ++pp;
else if(pp == 0) // 패턴의 0부터 틀렸을 경우엔 텍스트(위 패턴) iterator만 증가시키고 pp는 0 그대로. 그리고 동시에 skip 배열 업데이트
skip[++pt] = pp;
else
pp = skip[pp]; // 아래 '검색 시작'에서의 의미와 동일함. 맞추다가 틀리게 되면, 맞춘 데 까지의 skip값을 가져와서(거기부터 재비교하기위해) 다시사용함.
// ABC ABD 일 때, C 가 인덱스 2인데, skip[2]는 결국 인덱스 1인 B의 skip값이 들어가므로..!(이것도 skip 배열은 1부터 시작하고, 문자열 배열은 0부터 시작하는 특징에 의해 비롯됨)
}
// 표 만들기 끝
// 검색 시작
pt = pp = 0;
while(txt[pt] != '\0' && pat[pp] != '\0') {
if(pp == 0)
printf("%2d ", counter++);
else
printf("%*s", 3, " ");
printf("%s\n", txt);
printf("%*s", 3 + pt, " ");
tmp = pt - pp; // 아레에서 + | 출력 뒤에 pt - pp 값을 사용해야하는데, 아래 포문을 거치고 나면 pt pp 값이 재설정되므로 그 전에 복사해놓기.
if(txt[pt] == pat[pp]) {
pt++; pp++;
putchar('+');
} else if(pp == 0) {// 패턴의 0부터 틀린경우 pt만 하나 증가하고 진행
pt++;
putchar('|');
}
else {
pp = skip[pp]; // 틀린경우, 텍스트의 해당자리부터 다시, 패턴을 재조합하여 검사
putchar('|');
}
putchar('\n');
printf("%*s%s\n", 3 + tmp, " ", pat);
}
if(pat[pp] == '\0')
return pt - pp;
// 검색 끝
return - 1;
}
int main() {
int idx;
char s1[256]; // 텍스트
char s2[256]; // 패턴
puts("브루트 포스법");
printf("텍스트 : ");
scanf("%s", s1);
printf("패턴 : ");
scanf("%s", s2);
idx = kmp_match(s1, s2);
if(idx == -1)
puts("텍스트에 패턴이 없습니다.");
else
printf("%d번째 문자부터 match합니다.\n", idx + 1);
return 0;
}
연습문제 Q_12 > Boyer - Moore 법을 구현한 프로그램의 검색 과정을 자세히 출력하는 프로그램을 작성하세요.
(정답 배낌. 이걸 기반으로 BM 공부해야함.)
// Q12 Boyer-Moore법으로 문자열 검색(검색 과정 출력)
#include <stdio.h>
#include <string.h>
#include <limits.h>
void _print(const char txt[], const char pat[], int txt_len, int pat_len, int pt, int pp)
{
int i = 0, k = 0;
if (pp != pat_len - 1)
printf(" ");
else {
printf("%2d ", pt - pp);
k = pt - pp;
}
for (i = 0; i < txt_len; i++)
printf("%c ", txt[i]);
putchar('\n');
printf("%*s%c\n", pt * 2 + 4, "", (txt[pt] == pat[pp]) ? '+' : '|');
printf("%*s", (pt - pp) * 2 + 4, "");
for (i = 0; i < pat_len; i++)
printf("%c ", pat[i]);
printf("\n\n");
}
int bm_match(const char txt[], const char pat[])
{
int pt;
int pp;
int txt_len = strlen(txt);
int pat_len = strlen(pat);
int skip[UCHAR_MAX + 1];
for (pt = 0; pt <= UCHAR_MAX; pt++)
skip[pt] = pat_len;
for (pt = 0; pt < pat_len - 1; pt++)
skip[pat[pt]] = pat_len - pt - 1;
// pt == pat_len - 1 /
while (pt < txt_len) {
pp = pat_len - 1;
while (_print(txt, pat, txt_len, pat_len, pt, pp), txt[pt] == pat[pp]) {
if (pp == 0)
return pt;
pp--;
pt--;
}
int a = skip[txt[pt]];
int b = pat_len - pp;
pt += (skip[txt[pt]] > pat_len - pp) ? skip[txt[pt]] : pat_len - pp;
}
return -1;
}
int main(void)
{
int idx;
char s1[256]; // 텍스트 /
char s2[256]; // 패턴 /
puts("Boyer-Moore법");
printf("텍스트: ");
scanf("%s", s1);
printf("패턴: ");
scanf("%s", s2);
idx = bm_match(s1, s2);
if (idx == -1)
puts("텍스트에 패턴이 없습니다.");
else
printf("%d번째 문자와 일치합니다.\n", idx + 1);
return 0;
}
//내 코드. 정답아님 구현안함.
//
//#include <stdio.h>
//#include <string.h>
//#include <limits.h>
//
//int bm_match(const char txt[], const char pat[]) {
//
// int pt; // txt 커서
// int pp; // pat 커서
// int txt_len = strlen(txt); //txt 문자 개수
// int pat_len = strlen(pat); //pat 문자 개수
// int skip[UCHAR_MAX + 1]; // 건너뛰기 표
//
// for(pt = 0; pt <= UCHAR_MAX; pt++) {
// skip[pt] = pat_len; // 전부 길이 n으로
// }
//
// for(pt = 0; pt < pat_len - 1; pt++) { // 마지막 문자는 돌지 않음. 따라서 마지막 문자는 값이 n 그대로
// skip[pat[pt]] = pat_len - pt - 1;
// }
//
// // 여기까지, pt == pat_len - 1
//
// while(pt < txt_len) {
// pp = pat_len - 1;
// while(txt[pt] == pat[pp]) {
// if(pp == 0) // 0까지 같다는건 모두 같다는 것.
// return pt;
// pp--;
// pt--;
//
// }
// pt += (skip[txt[pt]] > pat_len - pp) ? skip[txt[pt]] : pat_len - pp;
// // 마지막 문자를 제외하고, 비교 과정에서 이미 텍스트에서 한번 등장한 패턴 안의 문자가 또 텍스트에서 다시 등장한 경우.
// // 원래의 skip 배열 값은 pat_len - pt - 1의 값으로 지정되어있는데 그것보다 더 큰 값이 나오게 된다는 건, 텍스트에서 등장한 문자가 다시 등장하게 되었다는 것.
// // 이렇게 해줘야 뒤로 안가고 앞으로 가게 해준다. (코드에서 위치지정은, 현재인덱스 + 이동할 거리 = 이동한 패턴의 마지막 문자 위치 이기 때문에)
// // 즉 패턴의 마지막 문자의 중복에 대한 경우는 처음부터 skip 배열 안에 n으로 지정하여, 현재 인덱스 + n = 다음 검사할 패턴의 마지막 문자 위치 라는 식을 도입해놨는데, 패턴의 마지막 문자 이외에 다른 문자들이 한번 이상 등장하게 되면, 현재 인덱스 + x 위치의 결과로 기존의 패턴위치보다 뒤로 갈 수 있는 경우가 리버스 경우가 생긴다. 그걸 방지하기 위한 코드인 것 같다.
//
// // 현재 비교하는 과정에서 두 문자가 다른데, 텍스트에 해당하는 문자가 패턴에 들어 있는 문자이긴 한데, 현재 비교 위치가 skip값인 lastindex 위치의 문자가 아닌 이미 그 문자 위치를 지나온 위치인 경우.
// // 현재 비교 결과가 달라서 skip 배열을 참고했더니, 패턴 안에 있는 문자야. 근데 이미 그 lastindex위치를 지나왔기 때문에 그 값을 쓸 순 없고(쓰면 제자리 또는 뒤로감), 현재 인덱스에서 남은 크기를 모두 더해서 앞으로 이동하게끔 해줌.
// // 예시 텍스트: ABECBBDEABDE 패턴: ABDE
//
// }
//
// return -1;
//}
//
//int main() {
// int idx;
// char s1[256]; // 텍스트
// char s2[256]; // 패턴
// puts("Boyer-Moore법");
// printf("텍스트 : ");
// scanf("%s", s1);
// printf("패턴 : ");
// scanf("%s", s2);
// idx = bm_match(s1, s2);
//
// if(idx == -1)
// puts("텍스트에 패턴이 없습니다.");
// else
// printf("%d번쨰 문자부터 match합니다.\n", idx + 1);
//}
연습문제 Q_13 > strstr 함수와 같은 기능을 하는 str_str 함수를 작성하세요.
char *str_str(const char *s1, const char *s2);
Q_13 BM으로.
#include <stdio.h>
#include <string.h>
#include <limits.h>
char * bm_match(const char txt[], const char pat[]) {
int pt; // txt 커서
int pp; // pat 커서
int txt_len = strlen(txt); //txt 문자 개수
int pat_len = strlen(pat); //pat 문자 개수
int skip[UCHAR_MAX + 1]; // 건너뛰기 표
for(pt = 0; pt <= UCHAR_MAX; pt++) {
skip[pt] = pat_len; // 전부 길이 n으로
}
for(pt = 0; pt < pat_len - 1; pt++) { // 마지막 문자는 돌지 않음. 따라서 마지막 문자는 값이 n 그대로
skip[pat[pt]] = pat_len - pt - 1;
}
// 여기까지, pt == pat_len - 1
while(pt < txt_len) {
pp = pat_len - 1;
while(txt[pt] == pat[pp]) {
if(pp == 0) // 0까지 같다는건 모두 같다는 것.
return &txt[pt];
pp--;
pt--;
}
pt += (skip[txt[pt]] > pat_len - pp) ? skip[txt[pt]] : pat_len - pp;
// 마지막 문자를 제외하고, 비교 과정에서 이미 텍스트에서 한번 등장한 패턴 안의 문자가 또 텍스트에서 다시 등장한 경우.
// 원래의 skip 배열 값은 pat_len - pt - 1의 값으로 지정되어있는데 그것보다 더 큰 값이 나오게 된다는 건, 텍스트에서 등장한 문자가 다시 등장하게 되었다는 것.
// 이렇게 해줘야 뒤로 안가고 앞으로 가게 해준다. (코드에서 위치지정은, 현재인덱스 + 이동할 거리 = 이동한 패턴의 마지막 문자 위치 이기 때문에)
// 즉 패턴의 마지막 문자의 중복에 대한 경우는 처음부터 skip 배열 안에 n으로 지정하여, 현재 인덱스 + n = 다음 검사할 패턴의 마지막 문자 위치 라는 식을 도입해놨는데, 패턴의 마지막 문자 이외에 다른 문자들이 한번 이상 등장하게 되면, 현재 인덱스 + x 위치의 결과로 기존의 패턴위치보다 뒤로 갈 수 있는 경우가 리버스 경우가 생긴다. 그걸 방지하기 위한 코드인 것 같다.
// 현재 비교하는 과정에서 두 문자가 다른데, 텍스트에 해당하는 문자가 패턴에 들어 있는 문자이긴 한데, 현재 비교 위치가 skip값인 lastindex 위치의 문자가 아닌 이미 그 문자 위치를 지나온 위치인 경우.
// 현재 비교 결과가 달라서 skip 배열을 참고했더니, 패턴 안에 있는 문자야. 근데 이미 그 lastindex위치를 지나왔기 때문에 그 값을 쓸 순 없고(쓰면 제자리 또는 뒤로감), 현재 인덱스에서 남은 크기를 모두 더해서 앞으로 이동하게끔 해줌.
// 예시 텍스트: ABECBBDEABDE 패턴: ABDE
}
return NULL;
}
int main() {
char* idx;
char s1[256]; // 텍스트
char s2[256]; // 패턴
puts("Boyer-Moore법");
printf("텍스트 : ");
scanf("%s", s1);
printf("패턴 : ");
scanf("%s", s2);
idx = bm_match(s1, s2);
if(idx == NULL)
puts("텍스트에 패턴이 없습니다.");
else
printf("%d번쨰 문자부터 match합니다.\n", idx - s1 + 1);
}
//제공된 정답은 브포방식.
연습문제 Q_14 > 텍스트 문자열 s1에서 가장 마지막에 나오는 패턴 문자열 s2를 검색하는 str_rstr 함수를 작성하세요. 반환하는 값은 텍스트에서 찾은 문자열의 첫 번째 문자에 대한 포인터로 합니다. 검색에 실패할 경우 널 포인터를 반환합니다.
char *str_rstr(const char *s1, const char *s2);
Q_14 // 브포로.
#include <stdio.h>
#include <string.h>
char *bf_match(const char txt[], const char pat[]) {
int pt = 0; // txt 커서
int pp = 0; // pat 커서
int pp_last = 0;
// 아래 while 문과 strlen의 동작방식은 같다. 결과도 당연히 같다. 길이는 이렇게 널문자를 대상으로찾는과정이기에, 함수 매개변수가 현재 배열인데, 포인터여도 아래 while문 strlen문 둘다 잘 동작한다. 하지만 sizeof는 당연히 다른거고 ㅋ.
while(txt[pt] != '\0')
pt++;
while(pat[pp] != '\0')
pp++;
// pt = strlen(txt);
// pp = strlen(pat);
pp_last = pp - 1; // pat의 끝자리
//시작은 각 문자열의 널문자부터인데 딱히 상관없을듯.
while(pt >= 0 && pp >= 0) {
if(txt[pt] == pat[pp]) {
pt--;
pp--;
} else {
pt = pt + pp_last - 1;
pp = pp_last;
}
}
if(pp == -1)
return &txt[pt + 1]; // 마지막으로 pt-- 작업을 했으므로 하나 증가해줘야해
return NULL;
}
int main() {
char *idx;
char s1[256]; // 텍스트
char s2[256]; // 패턴
puts("브루트 포스법");
printf("텍스트 : ");
scanf("%s", s1);
printf("패턴 : ");
scanf("%s", s2);
idx = bf_match(s1, s2);
if(idx == NULL)
puts("텍스트에 패턴이 없습니다.");
else
printf("%d번째 문자부터 match합니다.\n", idx - s1 + 1);
return 0;
}
// 제공된 정답 역시 Q_10의 브포 정답 기반.
공부 내용 정리
문자열
문자의 나열. 문자 하나만 있어도, 비어있어도 상관없음.
문자열 리터럴
C언어에서 문자의 나열을 2개의 큰따옴표로 묶은 것을 문자열 리터럴이라고 함. 문자열 안의 문자는 메모리 공간에 연속으로 배치됨.
컴퓨터는 문자열 리터럴의 끝을 나타내기 위해 널 문자(Null Character, '\0')를 자동으로 추가함. 널 문자 내부는 컴퓨터 환경이나 문자 코드에 관계없이 모든 비트의 값이 0이다.
※문자열 리터럴의 내용을 자유롭게 바꿀 수 없다. 그러기 위해선 문자열을 배열로 구현해야 한다.
문자열 리터럴의 메모리 영역 기간은 정적 메모리 영역의 기간과 같으므로 프로그램의 시작부터 끝까지 메모리 영역이 유지된다.
같은 문자열 리터럴이 여러 개 있는 경우에는 이를 각각 다른 메모리 영역에 넣어두는 컴퓨터 환경도 있고, 같은 영역에 넣어두고 공유하는 컴퓨터 환경도 있다.
문자열 리터럴은 변수가 아니라 상수의 성질을 가지고 있다. 즉, 문자열 리터럴이 저장된 메모리 영역에 값을 대입할 수 없다.
+ C언어에서 널 문자('\0')는 문자열의 끝을 나타낸다.
#include <stdio.h>
int main(void) {
char st[10];
st[0] = 'A';
st[1] = 'B';
st[2] = 'C';
st[3] = 'D';
st[4] = '\0';
st[5] = 'E';
printf("문자열 st에는 \"%s\"가 들어 있습니다.\n", st);
return 0;
}
Outpurt : 문자열 st에는 "ABCD"가 들어 있습니다.
문자열 초기화
문자열을 선언하면서 동시에 초기화도 가능하다.
1.
char st[10] = {'A', 'B', 'C', 'D', '\0'};
2.
char st[10] = "ABCD';
보통은 간편한 2번 방법을 많이 사용한다.
요소의 개수를 생략하고 문자열을 선언하면 초기화할 때 입력한 문자열의 요소 개수가 배열의 요소 개수가 된다.
char st[] = "ABCD"; //배열 st의 요소 개수는 5개(Null 문자까지)
포인터와 문자열
char st[] = "12345" // 배열에 의한 문자열 사용의 메모리 할당은 6바이트
char *pt = "12345" // 포인터에 의한 문자열 사용의 메모리 할당은 sizeof(char *) + 6바이트
포인터로 표현한 문자열은 문자열 리터럴을 저장하기 위한 영역 외에도 pt가 갖는 메모리 영역이 필요.
+ 위 설명은 바라보는 관점에 따라 맞는 말이긴 할 수 있으나, 정확한 설명은 맨 아래에 올려둔 '문자열 리터럴' 링크 확인.
문자열의 길이
컴퓨터는 배열에 저장된 문자열의 경우 널 문자까지 문자열로 인식한다. 다시말해 배열 전체를 문자열로 사용하지 않는다. 따라서 배열에 들어 있는 요소의 개수가 항상 문자열의 길이를 의미하지 않으므로 문자열의 길이만 구하는 알고리즘이 필요하다.
문자열의 첫 문자부터 널 문자까지 선형 검색을 하면 된다. 문자열의 끝은 널 문자이므로 찾은 널 문자의 인덱스는 문자열의 길이와 같다.
+ 문자열의 끝에는 반드시 널 문자가 있으므로 검색에 실패하는 경우는 없다.
C언어 표준 라이브러리
문자열의 길이를 구하는 strlen 함수가 있다.
문자열 안에 들어 있는 문자를 검색하는 함수로, strchr 함수와 strrchr 함수를 제공한다. strchr 함수는 가장 앞쪽의 문자를 검색하지만 strrchr 함수는 가장 뒤쪽의 문자를 찾는 차이점이 있고, 둘은 반환값으로 요소의 인덱스가 아니라 그 요소에 대한 포인터를 반환한다.
두 문자열의 대소 관계를 판단하는 함수로 strcmp와 strncmp를 제공한다.
각 문자를 앞에서부터 순서대로 비교하되, strcmp는 범위가 항상 처음부터 끝까지지만 strncmp는 세 번째 인수로 지정한 문자열의 길이만큼만 비교할 수 있다. 반환값은 같으면 0 다르면 음수와 양수의 값을 리턴하는데, 음수양수값의 크기는 컴퓨터 환경마다 다르다.
+ 컴퓨터는 정수 값인 아스키 코드값으로 문자를 구별한다.
브루트 포스법
문자열에서 문자열을 검색하는 데엔 브루트 포스법을 사용한다.
브루트 포스법은 선형 검색을 확장한 알고리즘이므로 단순법, 소박법이라고도 한다.
(설명하는 바는 선형이랑 다를 바가 없어보이긴 한데, 선형검색하면서 동시에 일일이 문자열의 모든문자를 매칭해나가는 과정이므로 그러는듯)
시간복잡도 : 텍스트의 문자 개수가 n이고 패턴의 문자 개수가 m이라고 할 때, O(mn)
KMP법
다른 문자를 만나면 패턴을 1칸씩 옮긴 다음 다시 패턴의 처음부터 검사하는 브루트 포스법과는 다르게 중간 검사 결과를 효율적으로 사용하는 알고리즘
텍스트와 패턴의 겹치는 부분을 찾아내어, 검사를 다시 시작할 위치를 구한다. 이런 방법으로 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높인다.
(패턴의 어디부터 시작할지를 계산하여, 패턴 전체를 옮기는 것도 계산해야한다)
하지만 몇 번째 문자부터 다시 검색을 시작할지를 패턴을 이동시킬 때마다 다시 계산한다면 높은 효율을 기대할 수 없으므로, 몇 번째 문자부터 다시 검색할지에 대한 값을 미리 표로 만들어 문제를 해결한다.
표를 작성할 땐 패턴 안에서 중복되는 문자의 나열을 먼저 찾아야 한다. 이 과정에서 KMP법을 사용한다.
정리 팁 >
패턴의 결과 여부를 통해 움직인다는 것을 인지해야해. (브루트포스도 그렇지만)
브루트 - 포스법과 다르게, KMP법에서 텍스트를 스캔하는 커서 pt는 다시 뒤로 돌아오지 않는다.
표 인덱스는 1부터 두고(사용), 문자열이나 패턴은 0부터 사용한다.
0 1 2 3 4 5
A B C A B D
1 2 3 4 5 6 에 값을 넣는다.
그리고 인덱스 안의 각 값은, 해당 까지만 맞았을 때(다음이 틀렸을 때) 몇번 인덱스부터(0부터 시작하는 인덱스) 재시작하는지를 나타낸다.
(이때, 틀린 경우, 패턴의 이터레이터가 0인 경우를 제외하고 나머지는 원본의 해당 이터레이터에서 패턴의 이터레이터만 재배치 후 재시작한다. 패턴 iterator = 0일때를 제외하고, 패턴을 조정한 뒤 원본의 틀린 부분부터 다시 재검하는것. 브루트 포스는 어디서 틀렸던 간에 원본에서 이번에 처음 검사를 인덱스 +1로 이동. 패턴의 0부터 틀린 경우엔 텍스트의 iterator만 증가시킨다.)
다시말해 표 F(k)의 값 의미는 k번째 인덱스에서 접두사와 접미사가 일치하는 최대길이.
(k는 1부터 시작하는 인덱스, 실제 가리키는 문자열은 0부터 시작)
정리 - 해당문자까지 일치했을 때, 다음문자를 어디서부터 재검하면되느냐의 값. 다른의미로는 일치하는 길이.
표 계산시엔, 일치하지 않으면 0, 일치하면 1씩 늘여가며 값 도출. => 0이면 일치X, 0보다 크면 일치하는 길이가 있다는 것
다른분의 설명
대박임..나랑 같은책으로 공부하셨는데 정리를 너무잘해주심 ㅠㅜ
sustainable-dev.tistory.com/53
시간복잡도 : 텍스트의 문자 개수가 n이고 패턴의 문자 개수가 m이라고 할 때, 가장 나쁜 경우에도 O(n)
Boyer-Moore 법
브루트 - 포스법을 개선한 KMP법보다 효율이 더 우수하기 때문에 실제 문자열 검색에 널리 사용하는 알고리즘.
패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정합니다.
-> 텍스트에서 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표를 미리 만들어야 한다.
무조건 패턴의 마지막문자부터 비교하는게 특징.
마찬가지로, '패턴옮기고, 인덱스 검사해 나가고' 반복.
패턴 문자열의 길이가 n일 때 옮길 크기는 아래와 같은 방법으로 결정한다.
(옮길 전제는, 현재 비교가 같지 않을 경우 라는 것. 그리고 여기서 말하는 '옮길 크기=x'는
현재인덱스 + x = 패턴 옮긴 이후 패턴의 마지막문자위치를 뜻함. ( 항상 패턴 전체가 옮겨지는 크기라고 생각하면 안됨 )
1. 텍스트에서, 패턴에 들어 있지 않은 문자를 만난 경우
- 패턴을 옮길 크기는 n입니다.
-> 패턴 전체를 무조건 n만큼 옮기는 게 아님. 설명이 조금 미흡함. '현재 검사하고 있는 텍스트의 문자 위치' 로부터 '다음에 검사할 패턴의 마지막 문자 위치' 가 n만큼 떨어질 수 있도록 패턴을 옮긴다는 것을 뜻함.
=> 현재 검사하고 있는 인덱스 + n = 다음에 검사할 패턴의 마지막 문자 위치
(코드를 보니 현재 검사하고 있는 위치에서 +n을 하고 있고, 이는 현재 검사 위치가 마지막 인덱스가 아닐 경우엔 전체패턴이 n만큼 움직이진 않음을 확인할 수 있음.)
2. 패턴에 들어 있는 문자를 만난 경우
- 마지막에 나오는 위치의 인덱스(=lastIndexOf)가 k이면 패턴을 옮길 크기는 n - k - 1이다.
-> 마찬가지로, 현재 인덱스 + (n - k - 1) = 다음에 검사할 패턴의 마지막 문자 위치
- 같은 문자가 패턴 안에 중복해서 들어 있지 않다면(= 마지막 문자에 해당하는 조건인듯하다) 패턴을 옮길 크기는 n입니다.
-> 마찬가지로 현재 위치 + n = 다음에 검사할 패턴의 마지막 문자 위치
(참고로, 패턴이 ABAC일지라도 B는 4- 2 - 1 = 2이고, C는 4이며, 건너뛰기 표를 제작하는 과정에서 포문이 패턴길이 - 1 ‘미만’이라 마지막 문자인 C에 대한 할당은 없음 = 마지막 문자에 해당하는 조건이라는 것.)
다른분의 친절한 설명
https://devwooks.tistory.com/12
시간복잡도 : 텍스트의 문자 개수가 n이고 패턴의 문자 개수가 m이라고 할 때, 가장 나쁜 경우에도 O(n)이며 평균적으로 O(n/m)
+ 알아본 방법은 배열 1개만 사용하여 알고리즘을 구현했지만, 2개의 배열을 사용하면 KMP법과 마찬가지로 배열을 만드는 데 복잡한 처리가 필요하므로 효과가 떨어진다. 1개의 배열을 사용하는 방법으로 간단하게 구현한 Boyer-Moore 법을 사용해도 충분히 빠르다.
세 알고리즘 가운데 가장 실용적인 문자열 검색 알고리즘은 간단하게 구현한(1개의 배열 사용) Boyer-Moore 법이고, 경우에 따라 브루트 -포스법을 사용하기도한다.
출처 - '자료구조와 함께 배우는 알고리즘 입문 C언어편' 도서
참고
문자열 리터럴 관련 참고
https://iamsuperwen.github.io/2018/06/06/book_head_first_c1/
입력 버퍼 참고
'[알고리즘 + 자료구조] > [Do it 자료구조와 함께 배우는 알고리즘]' 카테고리의 다른 글
| [ 알고리즘 ] Do it 자료구조와 함께 배우는 알고리즘 10장 정리 (0) | 2021.01.13 |
|---|---|
| [ 알고리즘] Do it 자료구조와 함께 배우는 알고리즘 9장 정리 (0) | 2021.01.07 |
| [알고리즘] Do it 자료구조와 알고리즘 7장 정리 (0) | 2020.12.06 |
| [알고리즘] Do it 자료구조와 알고리즘 6장 정리 2/2 (0) | 2020.11.27 |
| [알고리즘] Do it 자료구조와 알고리즘 5장 정리 (0) | 2020.10.28 |