1684. Jack's Last Word

gistfile1.cpp

#include <vector>
#include <iostream>
#include <string>

void prefix_function (const std::string & s, std::vector<int> & pi) 
{
	size_t length = s.length();
	pi.resize(length);
	for (size_t i = 1; i < length; ++i) 
	{
		int suff_length = pi[i-1];
		while (suff_length > 0 && s[i] != s[suff_length])
			suff_length = pi[suff_length-1];
		if (s[i] == s[suff_length])  ++suff_length;
		pi[i] = suff_length;
	}
}

void check_words(const std::string & init_word, const std::string & new_word, std::vector<std::string> & answer)
{
	std::string word = init_word + "#" + new_word;
	std::vector<int> pi;
	prefix_function(word, pi);
	size_t current_index = word.length() - 1;
	while(word[current_index] != '#')
	{
		size_t prefix_length = pi[current_index];
		if (prefix_length == 0)
		{
			answer.clear();
			return;
		}
		answer.push_back(word.substr(0, prefix_length));
		current_index -= prefix_length;
	}
}

int main()
{
	//freopen("C:\\temp\\input.txt", "r", stdin);
	std::string init_word, new_word;
	std::cin >> init_word;
	std::cin >> new_word;
	std::vector<std::string> answer;
	check_words(init_word, new_word, answer);
	if (answer.size() == 0)
	{
		std::cout << "Yes";
	}
	else
	{
		std::cout << "No" << std::endl;
		for(auto rit = answer.rbegin(); rit != answer.rend(); ++rit)
			std::cout << *rit << " ";
	}
	std::cout << std::endl;
	return 0;
}