11585 속타는 저녁 메뉴

https://www.acmicpc.net/problem/11585

11585번: 속타는 저녁 메뉴

KMP 알고리즘 문제

처음에 한칸한칸 모두 확인하니 75% 쯤에서 시간초과 발생

알고리즘 시간에 배운 KMP 알고리즘으로 해결해야 O(N+M) 시간으로 시간초과가 발생하지 않는다.

분명 머리로는 이해하고 납득했는데 코드가 이해가 안가서 한참 생각한 문제._.

 

푸는 방법을 글로 써내려가면,

환형 문자열의 문제들은 문자열을 두배해서 문제를 푸는 것이 일반적이라고 한다.

'I W A N T M E A T' 의 문자열을 'I W A N T M E A T I W A N T M E A T' 로 str의 문자열을 두배 늘린 2000000개 배열을 사용

---

그리고 KMP 알고리즘의 핵심인 pi 를 구해야한다. 문자열을 두배로 늘렸으니 pi 배열도 2000000개 사용

코드 이해하기가 정말 어려웠는데 i와 j를 포인터 (투포인터 처럼) 처럼 생각하니까 이해가 되었다.

i는 두번째 글자부터 맨 끝 글자까지를 의미하고, j는 움직이는 pi? 직접 움직이면서 같으면 늘리고 다르면 줄이는 느낌이다.

이걸보고 이해하는 사람이 있을까..

이해가 안가면 하나하나 따라가보는 방법도 좋다. (A A B A A A 로 이해했다.)

 

getPi() 함수 코드

char str[2000000];
int pi[2000000];

void getPi() {
	int j = 0;
	for (int i = 1; i < 2 * N; i++) {
		while (j > 0 && str[i] != str[j]) {
			j = pi[j - 1];
		}
		if (str[i] == str[j]) {
			pi[i] = ++j;
		}
	}
}

---

KMP 알고리즘 함수도 pi를 구하는 함수와 매우 유사하다.

이 문제에서는 주어진 문자열이 둘다 N개의 글자로 이루어져있기 때문에,str과 str2의 문자열이 같아지는 조건을 j == N 으로 설정하여 이 경우에만 cnt를 증가시켰다.

 

KMP 함수 코드

void KMP() {
	int j = 0;
	for (int i = 0; i < 2 * N; i++) {
		while (j > 0 && str[i] != str2[j]) {
			j = pi[j - 1];
		}
		if (str[i] == str2[j]) {
			j++;
			if (j == N) {
				cnt++;
				j = pi[j - 1];
			}
		}
	}
}

---

#define은 여기서 필요없다

굳이 for문을 한번 더 넣어서 n을 찾은 이유는 str, str2의 문자열이 전부 같을 경우에

str 문자열을 두번 이어붙였기 때문에 한번 더 cnt가 증가하므로 경우를 나눠주었다.굳이 for문을 한번 더 돌지 않아도 될 방법이 있을것같지만  KMP가 너무 힘들었다._.

 

전체코드

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

#define initialize(x, y) memset(x, y, sizeof(x));

int N, cnt;
char str[2000000];
char str2[1000000];
int pi[2000000];

int gcd(int a, int b) {
	int c;
	while (b != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

void getPi() {
	int j = 0;
	for (int i = 1; i < 2 * N; i++) {
		while (j > 0 && str[i] != str[j]) {
			j = pi[j - 1];
		}
		if (str[i] == str[j]) {
			pi[i] = ++j;
		}
	}
}

void KMP() {
	int j = 0;
	for (int i = 0; i < 2 * N; i++) {
		while (j > 0 && str[i] != str2[j]) {
			j = pi[j - 1];
		}
		if (str[i] == str2[j]) {
			j++;
			if (j == N) {
				cnt++;
				j = pi[j - 1];
			}
		}
	}
}

int main() {
	char input;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> input;
		str[i] = input;
		str[i + N] = input;
	}
	for (int i = 0; i < N; i++) {
		cin >> input;
		str2[i] = input;
	}

	getPi();
	KMP();

	int n = 0;
	for (int i = 0; i < N; i++) {
		if (str[i] == str2[i]) {
			n++;
		}
	}

	if (n == N) {
		int g = gcd(cnt - 1, N);

		cout << (cnt - 1) / g << "/" << N / g;
	}
	else {
		int g = gcd(cnt, N);

		cout << cnt / g << "/" << N / g;
	}
}