백준 6550 부분 문자열 c++ (문자열)

문제 출처 : https://www.acmicpc.net/problem/6550

6550번: 부분 문자열

문제

2개의 문자열 s와 t가 주어졌을 때 s가 t의 부분 문자열인지 판단하는 프로그램을 작성하라. 부분 문자열을 가지고 있는지 판단하는 방법은 t에서 몇 개의 문자를 제거하고 이를 순서를 바꾸지 않고 합쳤을 경우 s가 되는 경우를 이야기 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t가 빈칸을 사이에 두고 들어온다. s와 t의 길이는 10만을 넘지 않는다.

출력

입력된 s와 t의 순서대로 s가 t의 부분 문자열인 경우 Yes라 출력하고 아닐 경우 No라고 출력한다.

알고리즘 분류

• 문자열
• 그리디 알고리즘

풀이

kmp, 트라이 등의 부분 문자열 탐색 알고리즘에 비하면 아주아주 순한 맛 문제이다.

입력의 크기가 10만이기 때문에, 그냥 O(N)으로 통과할 수 있다.

s를 스택에 넣어놓고 t를 0부터 t.length()-1까지 탐색하면서 스택의 top과 만나면 pop하고,

스택의 크기가 0이 된다면 부분 문자열이 있는 경우이므로 종료하는 풀이가 있는데,

스택 필요 없이 그냥 s의 인덱스로만 t에서 만났을 때 +1해줘도 된다.

 

 

코드

#include <iostream>
#include <string>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	string a, b;
	while (cin >> a >> b) {
		int aIdx = 0;
		bool isTrue = false;
		for (int i = 0; i < b.length(); i++) {
			if (a[aIdx] == b[i]) {
				aIdx++;
			}
			if (aIdx == a.length()) {
				isTrue = true;
				break;
			}
		}
		if (isTrue) {
			cout << "Yes\n";
		}
		else {
			cout << "No\n";
		}
	}


	return 0;
}