(PAT 1077) Kuchiguse (字符串暴力枚举)

Bertha 。 2022-03-21 14:52 192阅读 0赞

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?

### Input Specification: ###

Each input file contains one test case. For each case, the first line is an integer N (2≤N≤100). Following are N file lines of 0~256 (inclusive) characters in length, each representing a character's spoken line. The spoken lines are case sensitive.

### Output Specification: ###

For each test case, print in one line the kuchiguse of the character, i.e., the longest common suffix of all N lines. If there is no such suffix, write `nai`.

### Sample Input 1: ###

3
    Itai nyan~
    Ninjin wa iyadanyan~
    uhhh nyan~

### Sample Output 1: ###

nyan~

### Sample Input 2: ###

3
    Itai!
    Ninjinnwaiyada T_T
    T_T

### Sample Output 2: ###

nai

解题思路:

寻找若干串字符串的最长公共后缀(包括空格),这题用暴力枚举就可以解决

首先取第一个字符串的末位,然后与若干字符串的末位进行比较,如有一串字符串末尾不符合,则退出循环

第一个末尾比较完成后,取第一个字符串的倒数第二位与其余字符串进行比较,直到达到最短的那串字符串遍历完成

最后将字符串反转

#include <iostream>
    #include <string>
    #include <algorithm>
    #include <string.h>
    using namespace std;
    string sentences[101];
    int main() {
    	int N;
    	char c;
    	scanf("%d", &N);
    	c = getchar();
    	for (int i = 0; i < N; ++i) {
    		getline(cin, sentences[i]);
    	}
    	string kuchikai = "";
    	int minLen = 0x7fffffff;
    	for (int i = 0; i < N; ++i) {
    		if (sentences[i].length() < minLen) {
    			minLen = sentences[i].length();
    		}
    	}
    
    	int index = 1;
    	while (index <= minLen) {
    		char commonWord = sentences[0][sentences[0].size() - index];
    		bool flag = true;
    		for (int i = 1; i < N; ++i) {
    			if (sentences[i][sentences[i].size() - index] != commonWord ) {
    				flag = false;
    				break;
    			}
    		}
    		if(flag == false) break;
    		kuchikai += commonWord;
    		index++;
    	}
    
    	if (kuchikai == "") cout << "nai" << endl;
    	else {
    		reverse(kuchikai.begin(), kuchikai.end());
    		cout << kuchikai << endl;
    	}
    
    	system("PAUSE");
    	return 0;