[C++] 알고스팟/문자열 검색 - 작명하기

문제 링크

https://algospot.com/judge/problem/read/NAMING

algospot.com :: NAMING

 

접두사와 접미사가 같은 문자열을 찾기 위해 KMP알고리즘의 부분 일치 테이블(혹은 failure function으로 불림)을 사용해야 합니다.

 

부분 일치 테이블은 문자열의 첫 번째와 두 번째 부분문자열부터 오른쪽으로 하나씩 늘려가며 접두사도 되고 접미사도 되는 문자열의 길이를 배열의 해당 인덱스에 넣어줍니다.

 

부분 일치 테이블을 구하고 나면 s의 접미사와 접두사가 같은 문자열이 a, ab가 있는 것을 확인할 수 있습니다.

문제에서는 전체 문자열 s의 접두사와 접미사가 되는 문자열이니 a는 해당이 되지 않고 ab가 정답이 됩니다.

또한 전체 문자열인 abcab도 접두사와 접미사가 될 수 있으므로 abcab 또한 정답이 됩니다.

 

 

예제 입력을 살펴보면 위의 경우보다 더 많은 문자열이 정답이 됩니다.

먼저 전체 문자열은 접두사와 접미사가 같기 때문에 가장 먼저 문자열의 길이를 정답으로 넣어줍니다.

그리고 다음의 위치로 pi[k-1]를 가르킵니다.

 

위에서 가르킨 pi의 값이 그 다음의 문자열 길이가 됩니다.

문자열 길이 9만큼 접두사와 접미사가 같은 다음 문자열이 나오기 때문입니다.

이렇게 k의 값을 정답으로 먼저 넣고 다음 k를 pi[k-1]로 가르키면서 k가 0이 될 때까지 반복해주면 답을 구할 수 있습니다.

 

구현 코드

 

	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <string>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
	using namespace std;
	//부분 일치 테이블
	vector<int> getPartialMatch(string N){
	int m = N.size();
	vector<int> pi(m, 0);
	int begin = 1, matched = 0;
	//비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분 일치를 모두 기록한다.
	while(begin + matched < m){
	if(N[begin+matched] == N[matched]){
	++matched;
	pi[begin+matched-1] = matched;
	}
	else{
	if(matched == 0)
	++begin;
	else{
	begin += matched - pi[matched-1];
	matched = pi[matched-1];
	}
	}
	}
	return pi;
	}
	vector<int> getPrefixSuffix(string s){
	vector<int> ret, pi = getPartialMatch(s);
	int k = s.size();
	while(k > 0){
	//s[..k-1]는 답이다.
	ret.push_back(k);
	//s[..k-1]의 접미사도 되고 접두사도 되는 문자열도 답이다.
	k = pi[k-1];
	}
	return ret;
	}
	int main(){
	fastio;
	string s, s1, s2;
	cin >> s1 >> s2;
	s = s1 + s2;
	vector<int> ret= getPrefixSuffix(s);
	for(int i=ret.size()-1;i>=0;i--)
	cout << ret[i] << " ";
	cout << endl;
	return 0;
	}

view raw naming.cpp hosted with ❤ by GitHub