문자열
프로그램에서 문자의 '나열'을 나타내는 것이 문자열이다.
이때 문자의 나열은 어떤 문자가 항상 있어야 하는 것은 아니다. 문자가 하나만 있어도 좋고, 비어 있어도 상관없다. 빈 문자도 문자열이다.
문자열 리터럴
"STRING"이나 "ABC" 처럼 문자의 나열을 2개의 큰따옴표(")로 묶은 것을 문자열 리터럴이라 한다. 문자열 안의 문자는 메모리 공간에 연속으로 배치된다.
문자열 리터럴 특징
-
문자열 리터럴의 자료형
문자열 리터럴의 자료형은 char형 배열이다. 그러나 문자열 리터럴의 표현식을 평가하여 얻는 자료형은char *형이고 그 값은 첫번째 문자에 대한 포인터이다. 예를 들어 문자열 리터럴 "STRING"을 평가하면 첫 번째 글자 'S'에 대한 포인터를 얻는다. -
문자열 리터럴의 메모리 영역 기간
문자열 리터럴의 메모리 영역 기간은 정적 메모리 영역의 기간과 같다. 그러므로 프로그램의 시작부터 끝까지 메모리 영역이 유지된다. -
같은 문자열 리터럴이 여러 개 있는 경우 컴퓨터에서 처리하는 방법
같은 문자열 리터럴이 여러 개 있는 경우에는 이를 각각 다른 메모리 영역에 넣어두는 컴퓨터 환경도 있고 같은 영역에 넣어두고 공유하는 컴퓨터 환경도 있다. -
상수의 성질을 갖는 문자열 리터럴
문자열 리터럴은 변수가 아니라 상수의 성질을 가지고 있다. 즉 문자열 리터럴이 저장된 메모리 영역에 값을 대입할 수 없다.
포인터와 문자열
많은 C언어 프로그램에서는 배열이 아니라 포인터로 문자열을 나타낸다.
#include <stdio.h>
#include <stdlib.h>
int main() {
const char* pt = "12345";
printf("포인터 pt는 \"%s\"를 가리킵니다.", pt);
printf("\n*pt = %d", *pt);
}결과 : 포인터 pt는 "12345"를 가리킵니다.
배열에 의한 문자열과 포인터에 의한 문자열이 갖는 메모리 영역의 크기를 비교하면 다음과 같다.
char st[] = "12345";
char *pt = "12345";
배열에 저장한 문자열은 6바이트의 메모리 영역을 갖지만, 포인터로 표현한 문자열은 문자열 리터럴을 저장하기 위한 영역 외에도 pt가 갖는 메모리 영역이 더 필요하다.
다시 말해 포인터로 표현한 문자열은 배열에 저장한 문자열보다 더 많은 메모리 영역을 차지한다.
문자열 리터럴을 가리키는 두 포인터의 값을 서로 교환하는 프로그램
#include <stdio.h>
void swap_ptr(const char** a, const char** b) {
const char *temp = *a;
*a = *b;
*b = temp;
}
int main() {
const char* s1 = "ABCD";
const char* s2 = "EFGH";
printf("포인터 s1 -> %s\n", s1);
printf("포인터 s2 -> %s\n\n", s2);
swap_ptr(&s1, &s2);
printf("포인터 s1 -> %s\n", s1);
printf("포인터 s2 -> %s\n\n", s2);
}매개변수 a,b의 자료형은 포인터(s1,s2)의 주소를 받아야 하기 때문에 char**형으로 정의한다.
브루트-포스법
문자열에서 문자열을 검색하는 알고리즘이다. 선형 검색을 확장한 알고리즘이다.
1번째 문자부터 순서대로 일치하는지 검사한다. 문자가 일치하면 계속해서 텍스트의 문자를 검색한다. 그러다가 다른 문자가 나타나면 검사를 중단하고, 검색할 텍스트의 위치를 1칸 뒤로 이동한다.
이 과정을 반복해서 문자를 찾는다.
#include <stdio.h>
int bf_match(const char txt[], const char pat[])
{
int pt = 0;
int pp = 0;
while (txt[pt] != '\0' && pat[pp] != '\0') {
if (txt[pt] == pat[pp]) {
pt++;
pp++;
}
else {
pt = pt - pp + 1;
pp = 0;
}
}
if (pat[pp] == '\0')
return pt - pp;
return -1;
}
int main() {
int idx;
char s1[256];
char s2[256];
printf("텍스트 : ");
scanf_s("%s", &s1);
printf("패턴 : ");
scanf_s("%s", &s2);
idx = bf_match(s1, s2);
if (idx == -1) printf("텍스트에 패턴이 없습니다.");
else printf("%d번째 문자부터 일치합니다.",idx+1);
}이미 검사를 진행한 위치를 기억하지 못하므로 브루트-포스법의 효율은 좋지 않다고 할 수 있다.
이 알고리즘의 시간 복잡도는 O(n) 이다. 단순한 알고리즘이지만 실제로 아주 빠르게 동작한다.
KMP법
다른 문자를 만나면 패턴을 1칸씩 옮긴 다음 다시 패턴의 처음부터 검사하는 브루트-포스법과는 다르게 중간 검사 결과를 효율적으로 사용하는 알고리즘이다.
그러나 다음에 공부할 Boyer-Moore법과는 성능이 같거나 좋지 않아 실제 프로그램에서는 거의 사용하지 않는다.
이 알고리즘의 시간 복잡도는 가장 나쁜 경우에도 O(n) 이다.
순서 파일을 읽어 들이며 검색할 때 많이 사용한다.
Booyer-Moore법
텍스트 안에서 패턴에 들어 있지 않은 문자를 찾으면 해당 위치까지의 문자는 건너뛴다.
이 알고리즘은 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표를 만들어야 한다.
옮길 크기는 아래와 같은 방법으로 결정한다.
패턴에 들어 있지 않은 문자를 만난 경우
1. 패턴을 옮길 크기는 n(패턴의 크기)이다. 'X'는 패턴에 들어 있지 않으므로 4만큼 옮긴다.
패턴에 들어 있는 문자를 만난 경우
1. 마지막에 나오는 위치의 인덱스가 k이면 패턴을 옮길 크기는 n-k-1이다. 'A'는 패턴의 두 곳에 들어 있지만 마지막 인덱스를 기준으로 하여 패턴을 1만큼 옮긴다.
2. 같은 문자가 패턴 안에 중복해서 들어있지 않다면 ("ABAC"의 'C'는 패턴 안에 1개만 들어있다) 패턴을 옮길 크기는 n(패턴의 크기) 이다.
실습 프로그램
#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; // 표 작성
for (pt = 0;pt < pat_len - 1;pt++) skip[pat[pt]] = pat_len - pt - 1;
while (pt < txt_len) {
pp = pat_len - 1;
while (txt[pt] == pat[pp]) {
if (pp == 0)
return pt;
pp--;
pt--;
}
pt += (skip[txt[pt]] > pat_len - pp) ? skip[txt[pt]] : pat_len - pp;
}
}
int main() {
int idx;
char s1[256];
char s2[256];
printf("텍스트 : ");
scanf_s("%s", s1);
printf("%s", s2);
scanf_s("%s", s2);
idx = bm_match(s1, s2);
if (idx == -1) printf("텍스트에 패턴이 없다");
else printf("%d번째 문자부터 일치한다", idx + 1);
}이 알고리즘의 시간 복잡도는 가장 나쁜 경우라도 O(n) 이고 평균적으로 O(n/m)이다.
세 알고리즘 가운데 가장 실용적인 문자열 검색 알고리즘은 이 Booyer-Moore법이다.
경우에 따라 브루트-포스법을 사용하기도 한다.
