Kuchiguse (20)

#include <iostream>
#include <cstring>
using namespace std;
char a[110][260];                            

int main(){
    int n,len,minlen=256,num=0;
    cin>>n;getchar();                                 //输入完个数n后会有个\n换行符，为了不让下面的for循环输入，用getchar()来接收\n
    for(int i=0;i<n;i++){
        gets(a[i]);                                   //字符串可能带空格，用cin与scanf的%s格式都会以空格作为输入结束而跳过后面的字符，而用gets()则以\n作为输入结束标志
        len=strlen(a[i]);
        if(len<minlen) minlen=len;                    //找出所有字符串中最短的一个
        for(int j=0;j<len/2;j++){                        
            char temp=a[i][j];                        //反转字符数组，变为找公共前缀
            a[i][j]=a[i][len-1-j];
            a[i][len-1-j]=temp;
        }
    }
    for(int i=0;i<minlen;i++){                        //判断所有字符串的第i个字符是否相等
        bool same=true;
        for(int j=1;j<n;j++){
            if(a[0][i]!=a[j][i]){                     //判断其余字符串的第i位是否等于第一个字符串的第i位
                same=false;
                break;
            }
        }
        if(same) num++;                              //所有字符串的第i位相等，则计数器加1
        else break;
    }

    if(num==0) cout<<"nai";
    else{
        for(int i=num-1;i>=0;i--)
            cout<<a[0][i];
    }

    return 0;
}

#include<string>
#include<iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    getchar();
    string res;
    getline(cin, res);
    string temp;
    for (int i = 1; i < n; i++) {
        getline(cin, temp);
        int same = 0;
        for (same = 0; same<res.size()&&same<temp.size(); same++) {
            if (res[res.size() - 1 - same] != temp[temp.size() - 1 - same]) {
                break;
            }
        }
        if (same == 0) {
            res = "nai";
            break;
        }
        res = res.substr(res.size()-same);
        //cout << res << endl;
    }
    cout << res;
    cin >> temp;
}

	}

//这题比较简单,字符串翻转后比较方便找公共字串,注意几点
1.getline和cin不一伙的,cin后的值,getline仍旧会读,所以先getline过掉第一行;
2.min(MinSize, v[i].size());不行,只好先int size = v[i].size();
3.结束条件=N表示全比过且成功 #include<bits/stdc++.h>
using namespace std;
int main(){
	int N;
	cin >> N;
    
	string tmp;//无用的第一行
	getline(cin,tmp);
	
    vector<string> v(N);
	int MinSize = INT_MAX;
	for (int i = 0; i<N; i++){
		getline(cin,v[i]);
		reverse(v[i].begin(),v[i].end());
		int size = v[i].size();
		MinSi敏感词(MinSize, size);
	}


	string res = "";
	for (int i = 0; i<MinSize; i++){
		int j = 1;
		for (; j<N; j++){
			if (v[j][i] != v[0][i])break;
		}
		if (j != N){
            break;
		}
		else{
			res = v[0][i] + res;
		}
	}
    
    
    if (res == ""){
        cout << "nai";
        return 0;
    }else{
        cout << res;
        return 0;
	}
	return 0;
}

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

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int N;
vector<string> s;
int main(int argc, char** argv) {
	cin >> N;
	for(int i = 0;i <= N;i++){
		string str;
		getline(cin,str);
		s.push_back(str);
	}
	bool flag = true;
	int i;
	for(i = 1;i <= s[1].size();i++){
		char c = s[1][s[1].size() - i];
	for(int j = 2;j < s.size();j++) {
		if(s[j][s[j].size() - i] != c){
			flag = false;
			break;
		}
	}
	if(flag == false){
		break;
	}
	} 
	for(int k = i - 1;k >= 1;k--){
		cout << s[1][s[1].size() - k];
	}
	if(i == 1){
		cout << "nai";
	}
	cout << endl; 
	return 0;
}

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

int main()
{     int N;     cin>>N;     string t;     getline(cin, t);     vector<string> v(N);     int minSize = INT_MAX;     for(int i=0;i<N;i++)     {         getline(cin,v[i]);         reverse(v[i].begin(),v[i].end());         int size = v[i].size();         minSi***(minSize, size);     }     string result = "";     for(int i=0;i<minSize;i++)     {         int j=1;         for(;j<N;j++)             if(v[j][i] != v[0][i])                 break;         if(j != N)             break;         else             result = v[0][i] + result;     }     if(result == "")         cout<<"nai";     else         cout<<result;     return 0;
}

	

#include<bits/stdc++.h>
using namespace std;

const int Max=110;

int main() {
	int n,l[Max],L=256;
	cin>>n;
	getchar();
	string str[Max],answer;
	for(int i=0; i<n; i++) {
		getline(cin,str[i]);
		reverse(str[i].begin(),str[i].end());
		l[i]=str[i].size();
		L=min(L,l[i]);
	}
	for(int i=0; i<L; i++) {
		for(int j=1; j<n; j++) {
			if(str[0][i]!=str[j][i]) {
				break;
			} else {
				if(j==n-1) {
					answer+=str[0][i];
				}
			}
		}
	}
	if(answer!="") {
		reverse(answer.begin(),answer.end());
		cout<<answer<<endl;
	} else {
		cout<<"nai"<<endl;
	}
	return 0;
}

字典树  。。。。。。。。。。。    菜鸡的泪水
import java.io.StringBufferInputStream;
import java.io.*;
import java.util.*;
class Trie2 {
    Trie2[] childs;
    boolean isEnd;
    int len;
    int next;
    public Trie2(){
        isEnd = false;
        childs = new Trie2[256];
        len =0;
        next = 0;
    }
    public void insert(String word) {
        char [] sc = word.toCharArray();
        Trie2 root = this;
        for(int i = 0;i<sc.length;i++){
            int index = sc[i];
            if(root.childs[index]== null){
                Trie2 node = new Trie2();
                root.childs[index] = node;
                root.len++;
                root.next = index;
            }
            root = root.childs[index];
            if(i == sc.length-1){
                root.isEnd = true;
            }
        }
    }
    public boolean search(String word) {
        char[]sc = word.toCharArray();
        Trie2 root = this;
        for(int i = 0;i<sc.length;i++){
            int index = sc[i];
            if(root.childs[index] == null){
                return false;
            }
            root = root.childs[index];
        }
        if(root.isEnd == true){
            return true;
        }else{
            return false;
        }

    }
    public boolean startsWith(String prefix) {
        char[]sc = prefix.toCharArray();
        Trie2 root = this;
        for(int i = 0;i<sc.length;i++){
            int index = sc[i];
            if(root.childs[index] == null){
                return false;
            }
            root = root.childs[index];
        }
        return true;

    }

    public String find(){
        Trie2 root = this;
        StringBuilder sb =new StringBuilder();
        // System.out.print("dfs");
        
        while(root.len == 1){
            sb.append((char)root.next);
            if(root.isEnd == true){
                break;
            }
            if(root.childs[root.next] == null){
                break;
            }else{
            root = root.childs[root.next];
            }
        }
        return sb.toString();
    }
}

public class Main {
    static BufferedReader in =new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st =new StreamTokenizer(in);
    static StringTokenizer tokenizer;
    public static int nextInt() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
    public static String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(in.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public static void main(String[] args) throws IOException{
          int n =Integer.parseInt(in.readLine());
        Trie2 root  = new Trie2();
          for(int i = 0 ;i<n;i++){
              String str = in.readLine();
              StringBuilder sb = new StringBuilder(str);
              String temp =sb.reverse().toString();
              root.insert(temp);
          }
      StringBuilder  sb2 = new StringBuilder(root.find()).reverse();
        if(sb2.toString().length() == 0){
            System.out.print("nai");
        }else{
          System.out.println(sb2.toString());
        }
    }
}

更多PAT甲级题解--acking-you.github.io

题目

OJ平台

题目大意

题目大意很简单，就是给出很多句话，要你分析，最长的公共后缀。

• 这个地方难在输入的处理，注意输入如果用的 getline() 接收的一行，则前面一般不能有别的输入方式，否则会起冲突，导致 getline() 并未抢到值。那么怎么解决呢？用 scanf("%d\n") 限定输入的分隔符，这样就不会有冲突了！

代码解析

Input输入处理

void Input() {
    scanf("%d\n", &N);
    for (int i = 0; i < N; i++) {
        getline(cin, s[i]);
        //顺便求出最大的长度方便后续遍历，
       //实际上求出最小长度是最好，这样就不用再后续判断了。
        MaxSize = max(MaxSize, (int)s[i].size());
    }
}

print输出处理

void print() {
    string res = "";//普通的迭代循环判断
    for (int i = 1; i <= MaxSize; i++) {
        if (s[0].size() < i)
            break;
        bool f = true;
        string cmp = s[0].substr(s[0].size() - i, i);
        for (int j = 0; j < N; j++) {
            int len = s[j].size();
            if (len < i)
                goto end;
            if (cmp != s[j].substr(len - i, i)) {
                f = false;
                break;
            }
        }
        if (f)
            res = cmp;
    }
end:
    res = (res == "") ? "nai" : res;
    cout << res;
}

整合代码得出答案

效率还挺好

#include<bits/stdc++.h>
using namespace std;
int N;
int MaxSize;
string s[101];
//@输入处理
void Input() {
    scanf("%d\n", &N);
    for (int i = 0; i < N; i++) {
        getline(cin, s[i]);
        MaxSize = max(MaxSize, (int)s[i].size());
    }
}
//@输出处理
void print() {
    string res = "";
    for (int i = 1; i <= MaxSize; i++) {
        if (s[0].size() < i)
            break;
        bool f = true;
        string cmp = s[0].substr(s[0].size() - i, i);
        for (int j = 0; j < N; j++) {
            int len = s[j].size();
            if (len < i)
                goto end;
            if (cmp != s[j].substr(len - i, i)) {
                f = false;
                break;
            }
        }
        if (f)
            res = cmp;
    }
end:
    res = (res == "") ? "nai" : res;
    cout << res;
}
int main() {
    Input();
    print();
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<string> list;
vector<char> ans;
int n;
int main(int argc, const char * argv[]) {
    cin>>n;
    string temp;
    int b=0;
    char t;
    getline(cin, temp);
    for (int i=0; i<n; i++) {
        getline(cin, temp);
        list.push_back(temp);
    }
    for (int i=1; i<255; i++) {
        auto it1=list[0].end();
        t=*(it1-i);
        for (int j=0;j<n;j++) {
            auto it1=list[j].end();
            if (t!=*(it1-i)) {
                b=1;
                break;
            }
        }
        if (b==0) {
            ans.insert(ans.begin(), t);
        }else
            break;
    }
    
    if (ans.size()==0) {
        cout<<"nai";
    }else{
        for (auto it=ans.begin(); it<ans.end(); it++) {
            cout<<*it;
        }
    }
    return 0;
}

store = []
n = int(input())
length = 999999999
for i in range(n):
    x = list(str(input()))
    x.reverse()
    if len(x) < length:
        length = len(x)
    store.append(x)
res = []
for i in range(length):
    cm = store[0][i]
    for j in range(1, len(store)):
        if store[j][i] != cm:
            break
        if j == len(store)-1 and store[j][i] == cm:
            res.append(cm)
    else:
        continue
    break
res.reverse()
if len(res) > 0:
    print("".join(res))
else:
    print("nai")

暴力求最长公共子串，时间复杂度：O(n*len)

#include <cstdio>
#include <iostream>
using namespace std;
int main() {
  int n;
  scanf("%d", &n);
  getchar();  // eat enter
  string strs[n];
  int minlen = 256;
  for (int i = 0; i < n; i++) {
    getline(cin, strs[i]);
    if (strs[i].size() < minlen) minlen = strs[i].size();
  }
  int pos;
  bool same = true;
  // 垂直遍历字符串数组
  int poivt_size = strs[0].size();
  for (pos = 1; pos <= minlen; pos++) {
    same = true;
    for (int i = 1; i < n; i++) {
      if (strs[0][poivt_size - pos] != strs[i][strs[i].size() - pos]) {
        same = false;
        break;
      }
    }
    if (!same) break;
  }
  if (pos == 1) {
    printf("nai");
    return 0;
  }
  for (int i = pos - 1; i >= 1; i--) {
    printf("%c", strs[0][poivt_size - i]);
  }
  return 0;
}