[백준] 2902 KMP는 왜 KMP일까?

문제링크] https://www.acmicpc.net/problem/2902

2902번: KMP는 왜 KMP일까?

---

문제요약

Knuth-Morris-Pratt 와 같이 긴 형태를 KMP 처럼 이니셜의 짧은 형태로 변환하는 문제입니다.

풀이

문제 해결을 위해서는 문자열 처리에 대해서 알아야 합니다.

 

오늘 사용할 함수는 strtok() 함수입니다.

strtok(대상문자열, 기준문자);
    - char *strtok(char *_String, char const *_Delimiter);
    - 자른 문자열을 반환, 더 이상 자를 문자열이 없으면 NULL을 반환

strtok 함수는 char* 형태의 문자열과 기준 문자를 매개변수로 받습니다. 그리고 char 포인터를 반환하기 때문에 char 포인터를 선언하여 while문을 돌면서 갱신해주면서 이용하면 됩니다.

 

char *tok = strtok(str, "-");
	while (tok != nullptr) {
		printf("%c" ,tok[0]);
		tok = strtok(nullptr, "-");
	}

 

문제에서 하이픈("-")을 기준으로 문자열이 나뉘니 char *tok = strtok(str,"-"); 으로 char 포인터 tok 를 선언과 초기화해줍니다. 그 후 tok 가 nullptr를 가르킬 때까지 반복해줍니다. 이 때 while 문 안에서 tok = strtok(nullptr, "-");으로 초기화 해주는 데 그 이유는 strtok 함수가 기준문자를 만났을 때 기준문자를 NULL로 대체하기 때문입니다. 

 

strtok 함수 동작 그림

 

또한 tok가 포인터이기 때문에

printf("%c", tok[0]);

다음과 같이 인덱스를 통한 접근이 가능합니다.

 

strtok 함수를 이용할 때에 "기준문자가 NULL로 대체" 된다는 것을 꼭 기억해야 됩니다.

---

소스코드는 C/C++로 작성되었습니다.

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

int main() {
	char str[101];
	
	scanf("%s", &str);

	char *tok = strtok(str, "-");
	while (tok != nullptr) {
		printf("%c" ,tok[0]);
		tok = strtok(nullptr, "-");
	}

	return 0;
}