最长公共字符串后缀

题目 最长公共字符串后缀

image-f827fdd1

思路分析

代码实现

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNextInt()){
            int n=sc.nextInt();
            if(n==0)    break;

            String[] strs=new String[n];
            for(int i=0;i<n;i++)    strs[i]=sc.next();

            // 如果只有一个字符串，直接输出该字符串
            if (n == 1) {
                System.out.println(strs[0]);
                continue;
            }

            int start=-1;//公共前后缀的起始位置

            //以第一个为基准 从第二个开始遍历
            for(int i=1;i<strs.length;i++){
                int j=strs[i].length()-1;
                int k=strs[0].length()-1;

                while(j>=0 && k>=0 && strs[i].charAt(j)==strs[0].charAt(k)){
                    j--;
                    k--;
                }

                start=Math.max(start,k+1);
            }

            if(start!=-1){
                for(int i=start;i<strs[0].length();i++){
                    System.out.print(strs[0].charAt(i));
                }
            }

            System.out.println();
        }
    }
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        while (sc.hasNextInt()) {

            int n = sc.nextInt();

            if (n == 0) break;

            String[] strs = new String[n];

            for (int i = 0; i < n; i++)

                strs[i] = sc.next();

            StringBuilder sb = new StringBuilder(); // 创建 StringBuilder 用于存储公共后缀

            // 从第一个字符串的末尾开始向前遍历字符

            for (int i = 1; i <= strs[0].length(); i++) {

                boolean flag = true; // 标志位，判断当前字符是否在所有字符串中相同

                char c = strs[0].charAt(strs[0].length() - i); // 获取第一个字符串的倒数第 i 个字符

                // 遍历其余所有字符串，检查它们的相应位置的字符是否与 c 相同

                for (int j = 1; j < n; j++) {

                    // 如果当前字符串的长度小于 i，或字符不相同，则标记为 false

                    if (i > strs[j].length() || strs[j].charAt(strs[j].length() - i) != c) {

                        flag = false;

                        break; // 发现字符不相同，立即停止比较

                    }

                }

                if (flag) sb.append(c); // 如果所有字符串在该位置的字符都相同，则将该字符加入结果

                else break; // 如果不相同，则停止寻找公共后缀

            }

            sb.reverse(); // 由于我们是从后往前遍历字符，因此需要将结果反转

            System.out.println(sb);

        }

    }

}

同类题型

视频讲解

项目分区导航： 字符串长度 ⬅️ | 05-最长公共字符串后缀 | ➡️ 函数