풀이 z알고리즘을 이용하여 풀이할 수 있다. 정수의 범위로 배열을 만들고 입력받는 숫자를 인덱스로 하여 그 부분을 1로 만들고 첫 번째 배열에서 두 번째 배열이 있는지 확인하는 문제다. 이때 시계가 원형이기 때문에 a를 2번 이어 붙인 배열의 부분 배열에 b배열이 있는지 찾는다. cf) 배열을 이어 붙일 때 편의를 위해 배열을 string으로 만들어 + 연산자를 사용했다. 코드 #include #include using namespace std; const int MAX = 360000; string a, b; int Z[3 * MAX + 5]; void getZ(const string &str) { int L = 0, R = 0; int N = str.size(); for (int i = 1; i < ..

풀이 kmp의 실패 함수를 이용하여 풀이할 수 있다. 전체 문자열 길이를 L, 실패함수 배열을 pi (pi는 0 인덱스부터 시작)라 하면 L - pi[L-1]로 문제의 정답을 구할 수 있다. abcdab라는 문자열이 있을 때 pi[L-1]은 2이고 이 수는 반복되는 패턴 문자열인 abcd가 끝나고, 패턴 문자열 앞부분 ab 2 글자가 패턴 문자열에 붙은 거라고 볼 수 있다. 코드 #include char s[1000006]; int pi[1000006], L; int main() { scanf("%d %s", &L, s); int j = 0; for (int i = 1; i 0 && s[i] != s[j]) j = pi[j - 1]; if (s[i] == s[j]..

풀이 kmp알고리즘을 이용하여 풀 수 있다. kmp를 학교 자료구조 시간에 배웠는데 실패 함수 부분이 이해가 안 되어 포기했는데 다시 천천히 생각하니 이해할 수 있었다. 실패 함수도 kmp의 로직과 비슷하게 앞에서 비교한 것을 다시 비교하지 않고 재사용한다. 이해가 안된다면, abacabaac 이 예제로 실패 함수가 어떻게 돌아가는지 생각해보자. 코드 코드는 여기를 참고했다. #include #include #include #include using namespace std; vector getPi(string p) { int m = p.size(), j = 0; vector pi(m, 0); for (int i = 1; i 0 && p[i] != p[j]) j ..