首页 > 试题广场 >

Kuchiguse (20)

[编程题]Kuchiguse (20)

热度指数：6774 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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?

输入描述:

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.

输出描述:

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".

示例1

输入

3
Itai nyan~
Ninjin wa iyadanyan~
uhhh nyan~

输出

nyan~

算法知识视频讲解

Java

牛客84347347号

字典树  。。。。。。。。。。。    菜鸡的泪水
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());
        }
    }
}

发表于 2022-08-04 16:58:15 回复(0)

Java

readingilove

public class Main{     public static void main(String[] args) {         java.util.Scanner input = new java.util.Scanner(System.in);         int N = input.nextInt();         String[] sentences = new String[N];         input.nextLine(); // 读取换行符         for (int i = 0; i < N; i++) {             sentences[i] = input.nextLine();         }                  int len = 0;         boolean flag = true;         while (flag) {             if (len == sentences[0].length()) {                 break;             }                          len++;             char ch = sentences[0].charAt(sentences[0].length() - len);             for (int i = 1; i < sentences.length && flag; i++) {                 if (len > sentences[i].length()) {                     len--;                     flag = false;                     break;                 }                                  if (sentences[i].charAt(sentences[i].length() - len) != ch) {                     len--;                     flag = false;                 }             }         }                  if (len == 0) {             System.out.print("nai");         } else {             System.out.print(sentences[0].substring(sentences[0].length() - len));         }                  input.close();     }
}