KMP2 BOJ 1701 - Cubeeditor (KMP, 실패함수) https://www.acmicpc.net/problem/1701 입력된 문자열에서 두 번 이상 나오는 부분 문자열의 길이중 최대를 출력하는 문제. abcabcabc 가 주어졌을 때, abc와 abcabc모두 가능하므로 둘 중 더 긴 abcabc의 길이인 6이 정답이다. 두 번 이상 나오는 부분 문자열의 길이 중 최대 -> 모든 부분 문자열 중에서 실패함수의 최대값 fail[n-1]까지 구하면서 인덱스0~1, 0~2, 0~3, ... 0~n-1 부분 문자열 중 실패함수를 모두 구할 수 있다. 따라서 시작지점이 0일때, 1일때, .... n-2일 때의 실패함수를 모두 확인해서 최대값을 출력하면 된다. #include #include #include using namespace std; const int M.. 2019. 11. 6. KMP 문자열 매칭 알고리즘. O(N+M) string parent, pattern; KMP(parent,pattern) : pattern의 위치를 반환하는 함수 parent 문자열의 idx i, pattern 문자열의 idx j에 대해 i를 0부터 1씩 증가시키며 pattern을 찾는 상황에서 현재 i에서 pattern 찾는 것에 실패했을 때, i를 한 칸 옮기고 j를 fail[j]칸 옮기며 문자열을 찾는 알고리즘이다. 실패함수를 이용해서 푸는 문제가 많다. 실패함수를 만드는 로직과 kmp에서 pattern의 위치를 뽑는 로직이 같은 점을 눈여겨 보자. #include #include #include using namespace std; vector makeTable(string pattern) { int p.. 2019. 9. 18. 이전 1 다음