KMP 알고리즘
2022. 5. 14. 01:32ㆍTIL💡/Algorithms
문제
https://www.acmicpc.net/problem/16916
#include <iostream>
#include <vector>
using namespace std;
string p, s;
vector<long long> pi((1e6) + 1);
void make_pi(string p) {
// i는 접두사, j는 접미사 인덱스
// pi 배열은 접두사와 접미사가 일치하는 최대 길이
long long i = 0, j = 1;
long long p_len = p.length();
pi[0] = 0;
while(j < p_len) {
if(p[i] == p[j]) {
pi[j++] = ++i;
}
else {
if(i == 0) {
pi[j++] = 0;
}
else {
// 이미 이전에 일치한 전적이 있다는 뜻이기 때문에 활용
// pi 배열에는 문자열 길이가 저장되기 때문에 pi[i -1]은 이미 검증된 공통 문자열의 다음 인덱스를 가리킴
i = pi[i - 1];
}
}
}
}
bool kmp() {
long long s_len = s.length();
long long p_len = p.length();
int i = 0, j = 0;
while(i < s_len) {
if(s[i] == p[j]) {
i++;
j++;
// 패턴 발견
if(j == p_len) {
return true;
}
}
else {
if(j != 0) {
j = pi[j - 1];
}
else {
i++;
}
}
}
return false;
}
int main() {
cin >> s >> p;
long long s_len = s.length();
long long p_len = p.length();
if(s_len < p_len) {
cout << 0 << '\n';
return 0;
}
make_pi(p);
// for(int i = 0;i < p_len;i++) {
// cout << pi[i];
// }
bool result = kmp();
if(result) {
cout << 1 << '\n';
}
else {
cout << 0 << '\n';
}
return 0;
}
참고
https://chanhuiseok.github.io/posts/algo-14/
https://injae-kim.github.io/dev/2020/07/23/all-about-kmp-algorithm.html
https://bblackscene21.tistory.com/2
'TIL💡 > Algorithms' 카테고리의 다른 글
[중급 알고리즘] 그리디 (연습) (0) | 2022.05.16 |
---|---|
[프로그래머스] 섬 연결하기 (0) | 2022.05.14 |
[백준] 1916: 최소 비용 구하기 (0) | 2022.05.13 |
[그래프 알고리즘] 다익스트라와 크루스칼의 차이 (0) | 2022.05.13 |
[백준] 1937: 욕심쟁이 판다 (0) | 2022.05.13 |