Java实现多字符串最长公共子串查询的技术求助

以下是完整的Java代码，实现了你需要的功能：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        byte n = input.nextByte();
        String[] words = new String[n];
        
        for (int i = 0; i < n; i++) {
            words[i] = input.next();
        }
        
        // 处理n=0的边界情况（题目输入应为正整数，做防御性处理）
        if (n == 0) {
            input.close();
            return;
        }
        
        // 找到最短字符串，最长公共子串长度不可能超过它
        String shortest = words[0];
        for (String word : words) {
            if (word.length() < shortest.length()) {
                shortest = word;
            }
        }
        
        String longestCommonSubstring = "";
        int maxLength = shortest.length();
        
        // 从最长可能的子串长度开始遍历，找到符合条件的就停止
        for (int len = maxLength; len > 0; len--) {
            // 遍历当前长度下的所有子串
            for (int start = 0; start <= shortest.length() - len; start++) {
                String candidate = shortest.substring(start, start + len);
                boolean isCommon = true;
                
                // 检查所有字符串是否都包含该子串
                for (String word : words) {
                    if (!word.contains(candidate)) {
                        isCommon = false;
                        break;
                    }
                }
                
                if (isCommon) {
                    longestCommonSubstring = candidate;
                    input.close();
                    System.out.println(longestCommonSubstring);
                    return;
                }
            }
        }
        
        // 无公共子串，输出空
        input.close();
    }
}

关键逻辑说明 #

• 基准选择：以输入中最短的字符串为基准，因为最长公共子串的长度不可能超过它，减少无效遍历。
• 从长到短遍历：优先检查更长的子串，一旦找到所有字符串都包含的子串，直接输出并终止程序，保证效率。
• 全局检查：对每个候选子串，遍历所有输入字符串验证存在性，只要有一个字符串不包含，就跳过该候选。

示例验证 #

• 示例1中，最短字符串是asdfg，从长度5开始检查，asdfg不在第二个字符串中；接着检查长度4的子串sdfg，确认所有字符串都包含后直接输出。
• 示例2中，遍历所有可能的子串长度后，未找到所有三个字符串共有的子串，最终输出空内容。

内容的提问来源于stack exchange，提问作者Phantom