백준 BOJ 7575 - 바이러스

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

7575번: 바이러스

KMP 3일차 그 두번째 문제

문제가 복잡하게 생겼는데 구현 자체는 그리 복잡하지는 않다.

 

입력되는 문자열 중 하나에서 길이가 K인 부분문자열 S'를 분리한 뒤,

다른 모든 문자열에 이 S' 이 포함되어있는지 세어주면 되는 문제이다.

 

KMP 알고리즘을 적용하면 생각보다 나이브하게 풀리니까 부분문자열 분리하거나 할때

괜히 복잡하게 고민하지 말고 그냥 O(N)으로 분리해주도록 하자.

 

찾는 문자열과 찾아지는 문자열 두개를 서로 헷갈려서

상당히 뇌절을 친 문제.

아무래도 아직 KMP를 확실히 익히지는 못했나보다.

 

처음에는 배열을 그대로 냅두고 인덱스만 적당히 넘겨줘서

부분문자열 S'를 만들고자 했는데,

여기서도 뇌절을 쳐서 그냥 새로운 배열을 하나 더 만들어서 해결했다.

 

여러모로 수난이 많았다만 본래 딱히 더러운 부분은 없는 문제기에

AC.

 

소스코드 펼쳐보기

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

int N,K;
vector<int> v[123];
int fail[1234] = {0};

bool kmp(vector<int> find, vector<int> arr){
	int N = find.size();
	int M = arr.size();
	memset(fail, 0, sizeof(fail));
	
	//puts("----------------------");
	//printf("find - ["); for(int i : find) printf("%d ", i); printf("]\n");
	//printf("arr  - ["); for(int i : arr)  printf("%d ", i); printf("]\n");
	
	
	for(int i=0,j=1; j<N; j++){
		while(i>0 && find[i] != find[j]) i = fail[i-1];
		if(find[i] == find[j]) fail[j] = ++i;
	}
	
	for(int i=0,j=0; j<M; j++){
		while(i>0 && find[i] != arr[j]) i = fail[i-1];
		if(find[i] == arr[j]){
			if(i == N-1){
				return 1;
			}
			else i++;
		}
	}
	return 0;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> N >> K;
	for(int i=0; i<N; i++){
		int a,b;
		cin >> a;
		for(int j=0; j<a; j++){
			cin >> b;
			v[i].push_back(b);
		}
	}
	
	for(int a=0; a<=v[0].size()-K; a++){
		vector<int> comp(v[0].begin()+a, v[0].begin()+a+K);
		
		bool flag = true;
		for(int b=1; b<N; b++){
			bool res1 = kmp(comp,v[b]);
			reverse(v[b].begin(), v[b].end());
			
			bool res2 = kmp(comp,v[b]);
			reverse(v[b].begin(), v[b].end());
			
			flag = flag && (res1 || res2);
		}
		
		if(flag){
			cout << "YES";
			return 0;	
		}
	}
	
	cout << "NO";
	return 0;
}

현재 중간에 2일을 비우고 KMP 문제를 풀고 있는데

딱 이정도 텀이 까먹을랑말랑 해서

적당한거같다.