백준 BOJ 11585 - 속타는 저녁 메뉴

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

11585번: 속타는 저녁 메뉴

 

바로 전에 풀었던 10266 - 시계 사진들과 상당히 유사한 문제

환형으로 이어지는 문자열에서 다른 문자열이 몇번 포함되는지 체크하는 문제이다.

 

환형을 일일히 구현하기는 상당히 복잡하기 때문에

그냥 문자열 A와 B가 있을때

A를 두번 이어붙인 A' 속에 B가 몇번이나 포함되는지 세면 된다.

 

몇번이나 포함되는지 세는것은 kmp 알고리즘의 구현에 해당한다.

 

조심해야할 부분으로써

1
A
A

와 같이 문자열 A와 B가 같은 입력에서는 문자열을 두배하고 비교하므로

세는 횟수가 한번 더 많아지게 되는데,

두배로 만든 A' 문자열의 마지막 인덱스를 탐색에서 제외하면 AC를 받을수 있다.

 

소스코드 펼쳐보기

#include <bits/stdc++.h>
using namespace std;

int fail[1234567] = {0};
char s1[2345678] = {0};
char s2[1234567] = {0};

int gcd(int a, int b){
	if(b==0) return a;
	return gcd(b,a%b);
}

int main(){
	int N;
	cin >> N;
	
	for(int i=0; i<N; i++){ cin >> s1[i]; s1[N+i] = s1[i]; }
	for(int i=0; i<N; i++){ cin >> s2[i]; }
	
	for(int i=0,j=1; j<N; j++){
		while(i>0 && s2[i] != s2[j]) i = fail[i-1];
		if(s2[i] == s2[j]) fail[j] = ++i;
	}
	
	int cnt = 0;
	for(int i=0,j=0; j<N*2-1; j++){
		while(i>0 && s1[j] != s2[i]) i = fail[i-1];
		if(s1[j] == s2[i]){
			if(i == N-1){
				cnt++;
				i = fail[i];
			}
			else i++;
		}
	}
	//printf("[%d]", cnt);
	int d = gcd(cnt,N);
	cout << cnt/d <<"/"<<N/d<<"\n";
}

아직 KMP 구현법을 까먹지 않았다는것을 확인(2)

한두군데 헷갈린 부분이 있기는 한듯