PAT 解题报告 1077. Kuchiguse (20)

1077. Kuchiguse 题目描述:

The Japanese language is notorious for its sentence ending particles. Personal preference of such particles can be considered as a reflection of the speaker’s personality. Such a preference is called “Kuchiguse” and is often exaggerated artistically in Anime and Manga. For example, the artificial sentence ending particle “nyan~” is often used as a stereotype for characters with a cat-like personality:

  • Itai nyan~ (It hurts, nyan~)
  • Ninjin wa iyada nyan~ (I hate carrots, nyan~)

Now given a few lines spoken by the same character, can you find her Kuchiguse?

抽象出来其实就是找N个字符串的最长公共后缀子串. 如果没有公共后缀就输出nai.

1077. Kuchiguse 算法分析:

遍历每个字符串, 与当前的目标“最长公共后缀”进行后缀的比较, 取两者的最长公共后缀.  时间复杂度是O( S1 + S2 + … + Sn ), Si 表示第i个字符串的长度.  AC代码如下:
#include <iostream>
#include <string>
#include <algorithm>

void gao(int n) {
	bool bInit = true;
	std::string strSuffix("");
	std::string strLine;
	while(n--) {
		std::getline(std::cin, strLine);
		if(bInit)
			strSuffix = strLine, bInit = false;
		else {
			int iLen = std::min(strSuffix.size(), strLine.size());
			int iStart1 = strSuffix.size() - 1;
			int iStart2 = strLine.size() - 1;
			while(iLen && strSuffix[iStart1] == strLine[iStart2])
				iLen--, iStart1--, iStart2--;
			strSuffix = strSuffix.substr(iStart1 + 1);
		}
	}
	if(strSuffix.empty())
		std::cout << "nai" << std::endl;
	else
		std::cout << strSuffix << std::endl;
	return ;
}

int main() {
	int N;
	std::cin >> N;
	getchar();
	gao(N);
	return 0;
}
Written on April 20, 2014