[C] 패턴 매칭 해결하기

다음 주어지는 영어 문장에서 특정한 문자열의 개수를 리턴하는 프로그램을 작성하여라.

ti를 검색하면, Start eating well with these eight tips for healthy eating, which cover the basics of

a healthy diet and good nutrition.

위 INPUT의 답은 4가 된다.

 

제약 사항

총 10개의 테스트 케이스가 주어진다.

문장의 길이는 띄어쓰기 포함 1000자를 넘어가지 않는다.

한 문장에서 검색하는 문자열의 길이는 최대 10을 넘지 않는다.

한 문장에서 하나의 문자열만 검색한다.

 

입력

첫 줄에는 테스트케이스의 개수가 주어지고 그 다음 줄에는 검색 할 문자열이 주어진다. 그 다음 줄에는 문장이 주어진다.

 

입력 예시

1

ti

Start eating well with these eight tips for healthy eating, which cover the basics of a

healthy diet and good nutrition

 

출력

각각의 테스트 케이스에 대하여 검색된 문자열의 개수를 출력하라.

 

출력 예시

4

 

해설

본 문제는 앞서 배운 패턴 매칭 알고리즘 중에서 어떠한 것을 사용하여도 풀 수 있다. 입력되는 문자열의 길이가 길지 않아 고지식한 패턴 검색 알고리즘을 사용한 해법만 제공한다.

.

 

🤍 풀이

#include<stdio.h>
#define TC 1

int main() {
	int T, i, j, tc_len, str_len, flag = 0, cnt;
	char tc[5000]= { "Start eating well with these eight tips for healthy eating, which cover the basics of a healthy dietand good nutrition" };	// 문자 배열
	char str[10] = { "ti" };	// 패턴

	for (T = 0; T < TC; T++) {
		tc_len = str_len = 0;

		while (str[str_len] != '\0')	// 검색할 문자열의 길이를 구한다
			str_len++;
		while (tc[tc_len] != '\0')		// 문장의 길이를 구한다.
			tc_len++;

		cnt = 0;
		for (i = 0; i < tc_len; i++) {
			flag = 0;
			if (tc[i] == str[0]) {		// 패턴의 첫 글자가 같으면
				for (j = 1; j < str_len; j++) {		// 첫 글자 이후 패턴의 길이만큼
					if (tc[i + j] != str[j]) {		// 일치하지 않음
						flag = 0;
						break;
					}
					else
						flag = 1;
				}
			}
			if (flag)
				cnt++;		// 패턴의 갯수
		}
		printf("#%d %d\n", T+1, cnt);

	}
	return 0;
}

Brute Force방식(문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교)

 

 

 

 

by SW expert academy