할껀하고놀자

문자열 검색 알고리즘. for문 한번만 돌기 때문에 좋다. #include #include using namespace std; vector makeTable(string pattern) { int j = 0; int patternSize = pattern.size(); vector table(patternSize, 0); for (int i = 1; i 0 && pattern[i] != pattern[j]) { j = table[j - 1]; } if (pattern[i] == pattern[j]) { table[i] = ++j; } } return table; } void KMP(string parent, string pattern) { ve..

KMP 알고리즘에 대한 공부를 끝마치고 문제를 풀기 위해 찾아봤더니 바로 적용할 수 있는 문제가 있었다. https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 일치한다면, i를 출력하는 식이다. www.acmicpc.net KMP 알고리즘만 알고 있다면 별로 어렵지 않게 풀 수 있었다. 처음 풀때 시간초과가 났는데 endl --> "\n" 을 해주어야 시간초과가 나지 않는다.. #include #include #include #include using namespace s..