字符串处理面试题：最长回文子串、最长公共前缀、字符串匹配

一、最长回文子串：如何找到字符串中的"对称之美"

回文串就像语文课上的回文诗，正着读反着读都一样。在字符串处理中，找到最长的回文子串是个经典问题。我们以Java语言为例，看看如何高效解决这个问题。

中心扩展算法是最直观的解法之一，它的时间复杂度是O(n²)。我们遍历字符串，把每个字符当作回文的中心，向两边扩展寻找最长回文。

public class LongestPalindrome {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            // 处理奇数长度回文（如"aba"）
            int len1 = expandAroundCenter(s, i, i);
            // 处理偶数长度回文（如"abba"）
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    
    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
    
    public static void main(String[] args) {
        LongestPalindrome solution = new LongestPalindrome();
        System.out.println(solution.longestPalindrome("babad")); // 输出 "bab"或"aba"
        System.out.println(solution.longestPalindrome("cbbd"));  // 输出 "bb"
    }
}

更高效的Manacher算法可以在O(n)时间内解决问题，但实现起来比较复杂。在实际面试中，掌握中心扩展算法通常就足够了。

二、最长公共前缀：寻找字符串家族的共同基因

想象一群字符串站在一起，我们要找出它们最长的共同开头部分。这个问题在构建字典树(Trie)等场景中很常见。让我们用Java来实现这个功能。

public class LongestCommonPrefix {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        
        // 以第一个字符串为基准
        String prefix = strs[0];
        
        for (int i = 1; i < strs.length; i++) {
            // 不断缩短前缀直到匹配当前字符串
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }
    
    public static void main(String[] args) {
        LongestCommonPrefix solution = new LongestCommonPrefix();
        String[] test1 = {"flower","flow","flight"};
        System.out.println(solution.longestCommonPrefix(test1)); // 输出 "fl"
        
        String[] test2 = {"dog","racecar","car"};
        System.out.println(solution.longestCommonPrefix(test2)); // 输出 ""
    }
}

这个算法的时间复杂度是O(S)，其中S是所有字符串中字符的总数。在最坏情况下，我们需要比较所有字符串的每个字符。

三、字符串匹配：从朴素算法到KMP的进化之路

字符串匹配是计算机科学中的基础问题，我们要在一个主串中查找子串出现的位置。让我们看看几种不同的实现方式。

首先是最朴素的暴力匹配算法：

public class NaiveStringMatch {
    public static int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        
        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }
            if (j == m) return i; // 找到匹配
        }
        return -1; // 未找到
    }
    
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        System.out.println(search(text, pattern)); // 输出 10
    }
}

朴素算法虽然简单，但最坏情况下时间复杂度是O(mn)。KMP算法通过预处理模式串，将时间复杂度降低到O(n+m)。下面是KMP算法的实现：

public class KMP {
    public static int search(String text, String pattern) {
        int[] lps = computeLPSArray(pattern);
        int i = 0; // text的索引
        int j = 0; // pattern的索引
        int n = text.length();
        int m = pattern.length();
        
        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if (j == m) {
                return i - j; // 找到匹配
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1;
    }
    
    private static int[] computeLPSArray(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0;
        int i = 1;
        lps[0] = 0;
        
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = len;
                    i++;
                }
            }
        }
        return lps;
    }
    
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        System.out.println(search(text, pattern)); // 输出 10
    }
}

四、应用场景与技术选型指南

这些字符串处理算法在实际开发中有着广泛的应用：

最长回文子串常用于文本分析、DNA序列分析等领域。在网络安全中，检测异常流量时也会用到类似技术。
最长公共前缀在构建搜索引擎、自动补全系统和文件路径处理中非常有用。比如，当用户输入搜索词时，系统可以快速找到所有可能的补全选项。
字符串匹配算法是文本编辑器、IDE和杀毒软件的基础。KMP算法在生物信息学中用于基因序列比对，Boyer-Moore算法则常用于文本搜索工具中。

技术选型建议：

对于简单场景，优先考虑实现简单的算法
处理大规模数据时，考虑更高效的算法
在内存受限环境下，注意空间复杂度
实际开发中，可以优先使用语言内置的字符串函数

五、性能分析与优化技巧

最长回文子串：
- 中心扩展法平均性能不错，但最坏情况下是O(n²)
- Manacher算法虽然复杂，但线性时间复杂度在大数据量时优势明显
- 优化技巧：预处理字符串，统一处理奇偶长度情况
最长公共前缀：
- 垂直扫描法（逐个字符比较）在某些情况下更高效
- 分治法可以将问题分解，适合并行处理
- 对字符串数组排序后，只需比较第一个和最后一个字符串
字符串匹配：
- 朴素算法适合短模式串
- KMP适合模式串中有较多重复的情况
- Boyer-Moore算法在实际应用中通常表现最好

六、常见陷阱与最佳实践

边界条件处理：
- 空字符串输入
- 所有字符串相同的情况
- 没有匹配项的情况
编码注意事项：
- 考虑Unicode字符和多字节编码
- 注意字符串不可变性带来的性能影响
- 在Java中，String.substring的复杂度是O(1)（Java 7之前是O(n)）
测试用例设计：
- 包含特殊字符的字符串
- 超长字符串测试性能
- 包含重复模式的字符串

七、总结与进阶学习建议

字符串处理是算法面试中的常客，掌握这些基础算法对编程能力的提升很有帮助。在实际开发中，我们还需要考虑：

结合具体业务场景选择合适的算法
权衡时间复杂度和空间复杂度
了解语言内置字符串函数的实现原理

对于想深入学习的开发者，建议研究：

后缀数组和后缀自动机
正则表达式引擎的实现
多模式串匹配算法（如AC自动机）
近似字符串匹配技术

敲码拾光专注于编程技术，涵盖编程语言、代码实战案例、软件开发技巧、IT前沿技术、编程开发工具，是您提升技术能力的优质网络平台。