#자료구조와 함께 배우는 알고리즘 입문 C언어 - 9

8장 문자열 검색

 

08-1 문자열의 기본

문자열이란?

문자의 나열 : 문자 하나만 있어도 좋고, 빈 문자열도 문자열

 

문자열 리터럴

문자의 나열을 2개의 큰따옴표(")로 묶은 것

 

문자열 리터럴의 자료형

char형 배열 : 문자의 리터럴의 표현식을 평가하여 얻는 자료형은 char*형이고 그 값은 첫 번째 문자에 대한 포인터

문자형 리터럴의 메모리 영역 기간

정적 메모리 영역의 기간과 같음. 프로그램 시작부터 끝까지 메모리 영역이 유지됨

상수의 성질을 갖는 문자열 리터럴

변수가 아니라 상수의 성질을 가지고 있음. 저장된 메모리 영역에 값을 대입할 수 없음

 

// 배열에 문자열 저장하기
int main(void)
{
	char st[10];
	st[0] = 'A';
	st[1] = 'B';
	st[2] = 'C';
	st[3] = 'D';
	st[4] = '\0';
	st[5] = 'X'; // [4]에 들어 있는 문자는 문자열의 끝을 나타내는 문자이므로 [5]는 출력되지 않는다 

	printf("문자열 st에는 \"%s\"가 들어 있습니다.\n", st);

	return 0;
}

// 문자열 초기화
char st[10] = {'A', 'B', 'C', 'D', '\0'};
char st[10] = "ABCD";

char st[128];
scanf_s("%s", st); // st는 첫 번째 문자에 대한 포인터이므로 & 연산자가 필요없음

 

포인터와 문자열

void swqp_ptr(char** x, char** y)
{
	char* tmp = *x;
	*x = *y;
	*y = tmp;
}
int main(void)
{
	char* s1 = (char*)"ABCD";
	char* s2 = (char*)"1234";
	printf("포인터 s1는 \"%s\"를(을) 가리킵니다.\n", s1);
	printf("포인터 s2는 \"%s\"를(을) 가리킵니다.\n", s2);

	swqp_ptr(&s1, &s2);

	puts("\n 포인터 s1과 s2의 값이 서로 교환했습니다.\n");
	printf("포인터 s1는 \"%s\"를(을) 가리킵니다.\n", s1);
	printf("포인터 s2는 \"%s\"를(을) 가리킵니다.\n", s2);

	return 0;
}

 

문자열의 길이

널 문자를 제외한 문자의 개수

int main(void)
{
	char *str = (char*)"1234456778";
	printf("이 문자열의 길이는 %d입니다.\n", strlen(str));
	
	return 0;
}

 

문자열애서 문자 검색하기

int main(void)
{
	char *str = (char*)"1234456778";
	char ch[] = "4";
	int nCh = ch[0];
	printf("이 문자열의 4은 %c 번째입니다.\n", strchr(str, nCh)); // 3번째 : str이 가리키는 문자열 가장 앞쪽에 있는 nCh를 찾습니다.
	printf("이 문자열의 4은 %c 번째입니다.\n", strrchr(str, nCh)); // 4번째 : str이 가리키는 문자열 가운데 가장 뒤쪽에 있는 nCh를 찾습니다.
    
	return 0;
}

 

문자열 비교

int main(void)
{
	printf("%d",strcmp("ABCD", "ABCE"));
	// 문자열이 같으면 0 반환, s1이 s2보다 크면 양의 정수, 작으면 음의 정수 반환
	return 0;
}

int main(void)
{
	printf("%d\n", strncmp("ABCDFEF", "ABCEFFF", 2));
   	// 0 : 2번째 문자까지의 대소 관계를 비교 "AB" "AB"
	// 문자열이 같으면 0 반환, s1이 s2보다 크면 양의 정수, 작으면 음의 정수 반환
	return 0;
}

 

08-2 부르트-포스법

이미 검사를 진행한 위치를 기억하기 못하므로 효율은 좋지 않습니다.

 

08-3 KMP법

검사했던 위치 결과를 버리지 않고 활용합니다.

 

08-4 Boyer-Moore법

패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정합니다.

 

// 문자열 검색 함수 strstr 함수
int main()
{
	char* p;
	puts("strstr 함수");
	char* s1 = (char*)"ANIMATION";
	char* s2 = (char*)"MA";

	p = strstr(s1, s2);
	if (p == NULL)
	{
		printf("패턴이 없습니다.\n");
	}
	else
	{
		int ofs = p - s1;
		printf("\n%s\n", s1);
		printf("%*s|\n", ofs, "");
		printf("%*s%s\n", ofs, "", s2);
	}
	return 0;
}
// strstr 함수 : s1이 가리키는 문자열에서 s2가 가리키는 문자열과 일치하는 문자열을 찾습니다.
// 가장 앞쪽에 나오는 문자열을 찾습니다.