백준 13506번 카멜레온 부분 문자열

문제

문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우가 아닌 위치에도 등장하는 T를 카멜레온 부분 문자열이라고 한다.

문자열 S가 주어졌을 때, 카멜레온 부분 문자열을 구하는 프로그램을 작성하시오.

예를 들어, S = "fixprefixsuffix"와 같은 경우에는 "fix"는 접두사, 접미사도 되고, 두 경우가 아닌 위치에도 등장하는 부분 문자열로도 등장한다.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져있으며, 길이는 106을 넘지 않는 자연수이다.

출력

가능한 카멜레온 부분 문자열 T 중에서 길이가 가장 긴 것을 출력한다. 만약, T가 존재하지 않으면 -1을 출력한다.

KMP 응용의 끝판 같은 느낌.

 

1. 접두어와 접미어의 일치를 구하기 위해 KMP 실패 함수를 통해 최장 일치 접미어를 구한다.

2. 접두어와 접미어가 둘다 아닌 경우를 제외하기 위해 맨 첫글자와 마지막 글자를 제외한 비교의 대상 문자열을 추출한다.

3.최장 접미어로부터 앞글자를 하나씩 줄여가면서 부분 문자열로 존재하는지 확인하는데, 이때 앞글자를 줄인 접미어가 

접두어와 일치하는지 계산해야한다. (즉 이 문자열이 접두어로써도 존재해야함)

4. 일치하면 그 문자열 출력 , 끝까지 일치하는 것이 없다면 -1 출력

 

#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> makeTable(string str)
{
	int size = str.size();
	vector<int> table(size, 0);
	int j = 0;
	for (int i = 1; i < size; i++)
	{
		while (j > 0 && str[i] != str[j])
		{
			j = table[j - 1];
		}
		if (str[i] == str[j])
		{
			table[i] = ++j;
		}
	}
	return table;
}

bool KMP(string parent, string pattern)
{
	int parentSize = parent.size();
	int patternSize = pattern.size();

	vector<int> table = makeTable(pattern);
	int j = 0;
	for (int i = 0; i < parentSize; i++)
	{
		while (j > 0 && parent[i] != pattern[j])
		{
			j = table[j - 1];
		}
		if (parent[i] == pattern[j])
		{
			if (j == patternSize - 1)
			{
				return true;
			}
			else
			{
				j++;
			}
		}
	}
	return false;
}

int main()
{
	
	string str;
	cin >> str;
	
	if (str.size() <= 2)
	{
		cout << -1 << endl;
		return 0;
	}

	vector<int> table = makeTable(str);


	string pattern = str.substr(str.size() - table[table.size() - 1], table[table.size() - 1]);
	string parent = str.substr(1,str.size()-2);

	for (int i = 0; i < pattern.size(); i++)
	{
		string str2 = pattern.substr(i, pattern.size() - i);
		string temp = str.substr(0, pattern.size() - i);
		if (str2 == temp && KMP(parent, str2))
		{
			cout << str2 << endl;
			return 0;
		}
		
	}
	cout << -1 << endl;
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}