KMP 알고리즘
2022. 5. 14. 01:32ㆍTIL💡/Algorithms
문제
https://www.acmicpc.net/problem/16916
16916번: 부분 문자열
첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.
www.acmicpc.net
#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/
알고리즘 - KMP 알고리즘 : 문자열 검색을 위한 알고리즘
@ 문자열을 검색하려면? : 패턴 매칭
chanhuiseok.github.io
https://injae-kim.github.io/dev/2020/07/23/all-about-kmp-algorithm.html
Injae's devlog
현실의 문제를 해결하는 엔지니어
injae-kim.github.io
https://bblackscene21.tistory.com/2
[알고리즘 공부] KMP Algorithm (문자열 검색 알고리즘)
밑에 보이는 예시는 KMP 알고리즘 사용 전인데 효율이 떨어져 보입니다. 텍스트와 패턴이 일치하는지 차례대로 순회하면서 비교해보기 때문에 시간복잡도는 O(문자열 길이 * 패턴 길이) = O(N)으로
bblackscene21.tistory.com
'TIL💡 > Algorithms' 카테고리의 다른 글
[중급 알고리즘] 그리디 (연습) (0) | 2022.05.16 |
---|---|
[프로그래머스] 섬 연결하기 (0) | 2022.05.14 |
[백준] 1916: 최소 비용 구하기 (0) | 2022.05.13 |
[그래프 알고리즘] 다익스트라와 크루스칼의 차이 (0) | 2022.05.13 |
[백준] 1937: 욕심쟁이 판다 (0) | 2022.05.13 |