[C++] 백준 16916번 부분 문자열
문제
문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.
예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.
문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.
입력
첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.
출력
P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.
풀이
kmp알고리즘을 이용해 O(N+M)에 구할 수 있다.
#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'
using namespace std;
string str, target;
vector<int> getPi(){
int len = target.length();
vector<int> pi(len, 0);
int j = 0;
for (int i=1; i<len; i++){
while (j > 0 && target[i] != target[j]){
j = pi[j-1];
}
if (target[i] == target[j]){
j++;
pi[i] = j;
}
}
return pi;
}
int solve(){
int j = 0;
vector<int> pi = getPi();
for (int i=0; i<str.length(); i++){
while (j > 0 && str[i] != target[j]){
j = pi[j-1];
}
if (str[i] == target[j]){
if (j == target.length()-1){
return 1;
}
else{
j++;
}
}
}
return 0;
}
int main(){
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// ifstream cin;
// cin.open("input.txt");
getline(cin, str);
getline(cin, target);
cout << solve();
}
Author And Source
이 문제에 관하여([C++] 백준 16916번 부분 문자열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lacram/C-백준-번-q11qisfc저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)