@이화월백 이 골라준 태그 문제풀이
오늘의 태그는 KMP되시겠다
https://www.acmicpc.net/problem/1305
1305번: 광고
세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광
www.acmicpc.net
KMP 알고리즘의 실패함수 개념에 대한 이해를 필요로 한다.
KMP 알고리즘에서 전처리로 사용되는 실패함수의 값 Fail[K] 는
처음부터 시작하는 길이 K+1짜리 부분 문자열에서 접두사와 접미사가 같아지는 최대 길이
라는 의미를 지닌다.
for(int i=0,j=1; j<N; j++){
while(i>0 && s[i] != s[j]) i = fail[i-1];
if(s[i] == s[j]) fail[j] = ++i;
}나는 실패함수의 구현을 이렇게 처리했는데,
https://yiyj1030.tistory.com/495
[알고리즘/ 파이썬] KMP 알고리즘 알아보기
KMP 알고리즘(Knuth-Morris-Pratt algorithm)이란 문자열 검색을 매우 빠르게 해주는 알고리즘이다. 특정 패턴이 주어졌을 때 전체 문자열을 빠르게 검색하여 그 패턴이 어디에 등장하는 지 찾아준다. KMP
yiyj1030.tistory.com
https://blog.encrypted.gg/1040
[실전 알고리즘] 0x1E강 - KMP
안녕하세요, 이번 시간부터 강의가 마칠 때 까지는 문자열 알고리즘을 다뤄보겠습니다. 미리 주의사항을 좀 알려드리자면 KMP의 경우 정말 헷갈립니다. 그렇기 때문에 이 강의를 보고 알듯말듯
blog.encrypted.gg
요 두분의 링크가 나에게 많은 도움이 되었다.
이러한 실패함수의 값을 담아놓은 배열을 구하면,
전체 문자열에 대한 Fail[N-1] 의 값은 전체 문자열에서 접두사와 접미사가 같은 부분,
즉 겹치는 부분의 길이를 의미하게 되므로, 해당 겹치는 부분의 길이를 빼주면 원래 의도했던 정답을 얻어낼 수 있다.
이해를 돕기 위해서 https://uang.tistory.com/33
BOJ 1305 광고
www.acmicpc.net/problem/1305 1305번: 광고 첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다. L은 백만보다 작거나 같은 자연수이다. www.acmicpc.net 위 문제는 길
uang.tistory.com
해당 글에서 사진을 가져와보았다.
소스코드 펼쳐보기
#include <bits/stdc++.h>
using namespace std;
int fail[1234567] = {0};
int main(){
int N;
cin >> N;
string s;
cin >> s;
for(int i=0,j=1; j<N; j++){
while(i>0 && s[i] != s[j]) i = fail[i-1];
if(s[i] == s[j]) fail[j] = ++i;
}
cout << N - fail[N-1];
return 0;
}
실패함수의 동작원리를 이해하기가 어려웠던 만큼, 기억해서 앞으로 사용하는데 어려움이 있을거 같아서
좀 주기적으로 KMP 문제를 풀면서 뇌속에 한번 넣어보고자 한다.