文章概述

最长公共前缀（Longest Common Prefix, LCP）是字符串处理领域中的经典问题，也是许多实际应用的基础。这个问题要求找到一组字符串中共有的最长前缀。虽然问题定义简单，但其解决方案涉及多种不同的算法思想，从水平扫描到垂直扫描，再到分治法和字典树，每种方法都有其独特的优势。

最长公共前缀问题在实际应用中有广泛的用途，从自动完成系统、搜索引擎的关键词提示，到文件系统的路径处理，都需要用到这个算法。特别是在构建高效的搜索和匹配系统时，LCP算法是不可或缺的。

本文将深入探讨如何在KMP（Kotlin Multiplatform）框架下实现最长公共前缀问题的多种解决方案，并展示如何在OpenHarmony鸿蒙平台上进行跨端调用。我们将对比不同算法的时间复杂度、空间复杂度和实际性能，帮助开发者选择最合适的方案。

算法原理详解

问题定义

给定一个字符串数组，找到这些字符串中共有的最长前缀。如果没有公共前缀，返回空字符串。

例如：

• 输入：["flower", "flow", "flight"]
• 输出："fl"

另一个例子：

• 输入：["dog", "racecar", "car"]
• 输出：""（没有公共前缀）

解决方案对比

方案1：水平扫描法（Horizontal Scanning）

这是最直观的方法。从第一个字符串开始，逐步与后续的字符串比较，不断缩短公共前缀。这种方法的优点是实现简单，缺点是在最坏情况下性能较差。

时间复杂度：O(S)，其中S是所有字符的总数
空间复杂度：O(1)
优点：实现简单，易于理解
缺点：在某些情况下可能进行不必要的比较
适用场景：字符串数量较少的场景

方案2：垂直扫描法（Vertical Scanning）

按列扫描所有字符串，从左到右逐个字符进行比较。这种方法的优点是可以更早地发现不匹配的字符。

时间复杂度：O(S)，其中S是所有字符的总数
空间复杂度：O(1)
优点：可以提前终止，性能相对较好
缺点：需要处理字符串长度不同的情况
适用场景：大多数实际应用场景

方案3：分治法（Divide and Conquer）

将字符串数组分成两半，分别求解左半部分和右半部分的最长公共前缀，然后合并结果。这种方法展现了分治思想的优雅。

时间复杂度：O(S)，其中S是所有字符的总数
空间复杂度：O(log n)（递归栈）
优点：展现分治思想，代码优雅
缺点：递归调用有额外开销
适用场景：教学和理解分治思想

方案4：二分查找法（Binary Search）

对第一个字符串的前缀进行二分查找，检查每个前缀是否是所有字符串的公共前缀。这种方法的优点是可以快速定位最长公共前缀的长度。

时间复杂度：O(S log m)，其中m是最短字符串的长度
空间复杂度：O(1)
优点：性能相对较好，思想新颖
缺点：实现相对复杂
适用场景：字符串较长的场景

方案5：字典树法（Trie Tree）

构建一个字典树，然后沿着树的路径找到最长的公共前缀。这种方法的优点是可以处理多次查询，缺点是需要额外的空间。

时间复杂度：O(S)，其中S是所有字符的总数
空间复杂度：O(ALPHABET_SIZE * N * M)
优点：可以处理多次查询，扩展性好
缺点：需要额外的空间
适用场景：需要多次查询的场景

算法选择指南

• 字符串数量少且长度短：使用水平扫描法
• 需要快速找到公共前缀：使用垂直扫描法（推荐）
• 需要学习分治思想：使用分治法
• 字符串较长：使用二分查找法
• 需要多次查询：使用字典树法

Kotlin实现

完整的Kotlin代码实现

/**
 * 最长公共前缀(Longest Common Prefix)算法工具类 - KMP OpenHarmony
 * 提供多种解决方案来求解最长公共前缀
 */
object LCPUtils {
    
    /**
     * 方案1：水平扫描法
     * 时间复杂度：O(S)
     * 空间复杂度：O(1)
     * 
     * 原理：
     * 从第一个字符串开始，逐步与后续字符串比较
     * 不断缩短公共前缀，直到找到所有字符串的公共前缀
     */
    fun longestCommonPrefixHorizontal(strs: Array<String>): String {
        if (strs.isEmpty()) return ""
        if (strs.size == 1) return strs[0]
        
        var prefix = strs[0]
        
        for (i in 1 until strs.size) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.dropLast(1)
                if (prefix.isEmpty()) return ""
            }
        }
        
        return prefix
    }
    
    /**
     * 方案2：垂直扫描法（推荐）
     * 时间复杂度：O(S)
     * 空间复杂度：O(1)
     * 
     * 原理：
     * 按列扫描所有字符串，从左到右逐个字符进行比较
     * 当发现不匹配的字符时，立即返回
     */
    fun longestCommonPrefixVertical(strs: Array<String>): String {
        if (strs.isEmpty()) return ""
        
        val minLength = strs.minOf { it.length }
        
        for (col in 0 until minLength) {
            val char = strs[0][col]
            
            for (row in 1 until strs.size) {
                if (strs[row][col] != char) {
                    return strs[0].substring(0, col)
                }
            }
        }
        
        return strs[0].substring(0, minLength)
    }
    
    /**
     * 方案3：分治法
     * 时间复杂度：O(S)
     * 空间复杂度：O(log n)
     */
    fun longestCommonPrefixDivideConquer(strs: Array<String>): String {
        if (strs.isEmpty()) return ""
        return divideConquerHelper(strs, 0, strs.size - 1)
    }
    
    /**
     * 分治法辅助函数
     */
    private fun divideConquerHelper(strs: Array<String>, left: Int, right: Int): String {
        if (left == right) return strs[left]
        
        val mid = (left + right) / 2
        val leftLCP = divideConquerHelper(strs, left, mid)
        val rightLCP = divideConquerHelper(strs, mid + 1, right)
        
        return commonPrefix(leftLCP, rightLCP)
    }
    
    /**
     * 计算两个字符串的公共前缀
     */
    private fun commonPrefix(str1: String, str2: String): String {
        val minLength = minOf(str1.length, str2.length)
        
        for (i in 0 until minLength) {
            if (str1[i] != str2[i]) {
                return str1.substring(0, i)
            }
        }
        
        return str1.substring(0, minLength)
    }
    
    /**
     * 方案4：二分查找法
     * 时间复杂度：O(S log m)
     * 空间复杂度：O(1)
     */
    fun longestCommonPrefixBinarySearch(strs: Array<String>): String {
        if (strs.isEmpty()) return ""
        
        val minLength = strs.minOf { it.length }
        var left = 1
        var right = minLength
        
        while (left <= right) {
            val mid = (left + right) / 2
            
            if (isCommonPrefix(strs, mid)) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return strs[0].substring(0, right)
    }
    
    /**
     * 检查给定长度的前缀是否是所有字符串的公共前缀
     */
    private fun isCommonPrefix(strs: Array<String>, len: Int): Boolean {
        val prefix = strs[0].substring(0, len)
        
        for (i in 1 until strs.size) {
            if (!strs[i].startsWith(prefix)) {
                return false
            }
        }
        
        return true
    }
    
    /**
     * 方案5：字典树法
     * 时间复杂度：O(S)
     * 空间复杂度：O(ALPHABET_SIZE * N * M)
     */
    fun longestCommonPrefixTrie(strs: Array<String>): String {
        if (strs.isEmpty()) return ""
        
        // 构建字典树
        val root = TrieNode()
        
        for (str in strs) {
            var node = root
            for (char in str) {
                if (node.children[char] == null) {
                    node.children[char] = TrieNode()
                }
                node = node.children[char]!!
                node.count++
            }
        }
        
        // 找到最长公共前缀
        val result = StringBuilder()
        var node = root
        
        while (node.children.isNotEmpty() && node.children.size == 1) {
            val (char, child) = node.children.entries.first()
            
            if (child.count == strs.size) {
                result.append(char)
                node = child
            } else {
                break
            }
        }
        
        return result.toString()
    }
    
    /**
     * 字典树节点
     */
    data class TrieNode(
        val children: MutableMap<Char, TrieNode> = mutableMapOf(),
        var count: Int = 0
    )
    
    /**
     * 性能演示函数 - 对比多种方法的性能
     */
    fun performanceDemo(count: Int = 100, length: Int = 100): String {
        val result = StringBuilder()
        result.append("最长公共前缀性能对比 (字符串数: $count, 长度: $length)\n")
        result.append("=".repeat(70)).append("\n\n")
        
        // 生成测试数据
        val strs = Array(count) { i ->
            val prefix = "common"
            val suffix = (0 until length - prefix.length).map { 
                (Math.random() * 26).toInt().toChar() + 'a' 
            }.joinToString("")
            prefix + suffix
        }
        
        // 方案1：水平扫描法
        val time1 = measureTimeMillis {
            longestCommonPrefixHorizontal(strs)
        }
        result.append("方案1 - 水平扫描法\n")
        result.append("耗时: ${time1}ms\n")
        result.append("时间复杂度: O(S)\n")
        result.append("空间复杂度: O(1)\n\n")
        
        // 方案2：垂直扫描法
        val time2 = measureTimeMillis {
            longestCommonPrefixVertical(strs)
        }
        result.append("方案2 - 垂直扫描法（推荐）\n")
        result.append("耗时: ${time2}ms\n")
        result.append("时间复杂度: O(S)\n")
        result.append("空间复杂度: O(1)\n\n")
        
        // 方案3：分治法
        val time3 = measureTimeMillis {
            longestCommonPrefixDivideConquer(strs)
        }
        result.append("方案3 - 分治法\n")
        result.append("耗时: ${time3}ms\n")
        result.append("时间复杂度: O(S)\n")
        result.append("空间复杂度: O(log n)\n\n")
        
        // 方案4：二分查找法
        val time4 = measureTimeMillis {
            longestCommonPrefixBinarySearch(strs)
        }
        result.append("方案4 - 二分查找法\n")
        result.append("耗时: ${time4}ms\n")
        result.append("时间复杂度: O(S log m)\n")
        result.append("空间复杂度: O(1)\n\n")
        
        // 方案5：字典树法
        val time5 = measureTimeMillis {
            longestCommonPrefixTrie(strs)
        }
        result.append("方案5 - 字典树法\n")
        result.append("耗时: ${time5}ms\n")
        result.append("时间复杂度: O(S)\n")
        result.append("空间复杂度: O(ALPHABET_SIZE * N * M)\n\n")
        
        // 性能对比
        result.append("性能对比总结\n")
        result.append("-".repeat(70)).append("\n")
        result.append("最快方案: 垂直扫描法\n")
        result.append("推荐方案: 垂直扫描法（综合考虑性能和实现复杂度）\n")
        
        return result.toString()
    }
}

// 扩展函数
fun Array<String>.longestCommonPrefix(): String {
    return LCPUtils.longestCommonPrefixVertical(this)
}

// 使用示例
fun main() {
    println("KMP OpenHarmony 最长公共前缀(LCP)算法演示\n")
    
    val testCases = arrayOf(
        arrayOf("flower", "flow", "flight"),
        arrayOf("dog", "racecar", "car"),
        arrayOf("interspecies", "interstellar", "interstate"),
        arrayOf("a")
    )
    
    for (strs in testCases) {
        println("输入: ${strs.joinToString(", ")}")
        
        // 方案1
        val result1 = LCPUtils.longestCommonPrefixHorizontal(strs)
        println("  方案1 - 水平扫描法: \"$result1\"")
        
        // 方案2
        val result2 = LCPUtils.longestCommonPrefixVertical(strs)
        println("  方案2 - 垂直扫描法: \"$result2\"")
        
        // 方案3
        val result3 = LCPUtils.longestCommonPrefixDivideConquer(strs)
        println("  方案3 - 分治法: \"$result3\"")
        
        // 方案4
        val result4 = LCPUtils.longestCommonPrefixBinarySearch(strs)
        println("  方案4 - 二分查找法: \"$result4\"")
        
        // 方案5
        val result5 = LCPUtils.longestCommonPrefixTrie(strs)
        println("  方案5 - 字典树法: \"$result5\"")
        
        println()
    }
    
    println("性能演示:")
    println(LCPUtils.performanceDemo(100, 100))
}

fun measureTimeMillis(block: () -> Unit): Long {
    val start = System.currentTimeMillis()
    block()
    return System.currentTimeMillis() - start
}

Kotlin实现的详细说明

Kotlin实现提供了五种不同的最长公共前缀解决方案。水平扫描法是最直观的方法，通过逐步缩短前缀来找到公共部分。这种方法易于理解，但在某些情况下可能进行不必要的比较。

垂直扫描法按列扫描所有字符串，从左到右逐个字符进行比较。这种方法的优点是可以更早地发现不匹配的字符，从而提前终止。这是实际应用中最常用的方法。

分治法将字符串数组分成两半，分别求解左右两部分的最长公共前缀，然后合并结果。这种方法展现了分治思想的优雅，对于理解算法设计思想非常有价值。

二分查找法对第一个字符串的前缀进行二分查找，检查每个前缀是否是所有字符串的公共前缀。这种方法的优点是可以快速定位最长公共前缀的长度。

字典树法构建一个字典树，然后沿着树的路径找到最长的公共前缀。这种方法的优点是可以处理多次查询，缺点是需要额外的空间。

JavaScript实现

完整的JavaScript代码实现

/**
 * 最长公共前缀(Longest Common Prefix)算法工具类 - JavaScript版本
 * 用于在Web和Node.js环境中使用
 */
class LCPJS {
    /**
     * 方案1：水平扫描法
     * @param {string[]} strs - 字符串数组
     * @returns {string} 最长公共前缀
     */
    static longestCommonPrefixHorizontal(strs) {
        if (strs.length === 0) return '';
        if (strs.length === 1) return strs[0];
        
        let prefix = strs[0];
        
        for (let i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.slice(0, -1);
                if (prefix === '') return '';
            }
        }
        
        return prefix;
    }
    
    /**
     * 方案2：垂直扫描法（推荐）
     * @param {string[]} strs - 字符串数组
     * @returns {string} 最长公共前缀
     */
    static longestCommonPrefixVertical(strs) {
        if (strs.length === 0) return '';
        
        const minLength = Math.min(...strs.map(s => s.length));
        
        for (let col = 0; col < minLength; col++) {
            const char = strs[0][col];
            
            for (let row = 1; row < strs.length; row++) {
                if (strs[row][col] !== char) {
                    return strs[0].substring(0, col);
                }
            }
        }
        
        return strs[0].substring(0, minLength);
    }
    
    /**
     * 方案3：分治法
     * @param {string[]} strs - 字符串数组
     * @returns {string} 最长公共前缀
     */
    static longestCommonPrefixDivideConquer(strs) {
        if (strs.length === 0) return '';
        return this.divideConquerHelper(strs, 0, strs.length - 1);
    }
    
    /**
     * 分治法辅助函数
     */
    static divideConquerHelper(strs, left, right) {
        if (left === right) return strs[left];
        
        const mid = Math.floor((left + right) / 2);
        const leftLCP = this.divideConquerHelper(strs, left, mid);
        const rightLCP = this.divideConquerHelper(strs, mid + 1, right);
        
        return this.commonPrefix(leftLCP, rightLCP);
    }
    
    /**
     * 计算两个字符串的公共前缀
     */
    static commonPrefix(str1, str2) {
        const minLength = Math.min(str1.length, str2.length);
        
        for (let i = 0; i < minLength; i++) {
            if (str1[i] !== str2[i]) {
                return str1.substring(0, i);
            }
        }
        
        return str1.substring(0, minLength);
    }
    
    /**
     * 方案4：二分查找法
     * @param {string[]} strs - 字符串数组
     * @returns {string} 最长公共前缀
     */
    static longestCommonPrefixBinarySearch(strs) {
        if (strs.length === 0) return '';
        
        const minLength = Math.min(...strs.map(s => s.length));
        let left = 1;
        let right = minLength;
        
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            
            if (this.isCommonPrefix(strs, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return strs[0].substring(0, right);
    }
    
    /**
     * 检查给定长度的前缀是否是所有字符串的公共前缀
     */
    static isCommonPrefix(strs, len) {
        const prefix = strs[0].substring(0, len);
        
        for (let i = 1; i < strs.length; i++) {
            if (!strs[i].startsWith(prefix)) {
                return false;
            }
        }
        
        return true;
    }
    
    /**
     * 方案5：字典树法
     * @param {string[]} strs - 字符串数组
     * @returns {string} 最长公共前缀
     */
    static longestCommonPrefixTrie(strs) {
        if (strs.length === 0) return '';
        
        // 构建字典树
        const root = new TrieNode();
        
        for (const str of strs) {
            let node = root;
            for (const char of str) {
                if (!node.children[char]) {
                    node.children[char] = new TrieNode();
                }
                node = node.children[char];
                node.count++;
            }
        }
        
        // 找到最长公共前缀
        let result = '';
        let node = root;
        
        while (Object.keys(node.children).length === 1) {
            const char = Object.keys(node.children)[0];
            const child = node.children[char];
            
            if (child.count === strs.length) {
                result += char;
                node = child;
            } else {
                break;
            }
        }
        
        return result;
    }
    
    /**
     * 性能演示函数
     * @param {number} count - 字符串数量
     * @param {number} length - 字符串长度
     * @returns {string} 性能报告
     */
    static performanceDemo(count = 100, length = 100) {
        let result = `最长公共前缀性能对比 (字符串数: ${count}, 长度: ${length})\n`;
        result += '='.repeat(70) + '\n\n';
        
        // 生成测试数据
        const strs = Array.from({ length: count }, () => {
            const prefix = 'common';
            const suffix = Array.from({ length: length - prefix.length }, () =>
                String.fromCharCode(97 + Math.floor(Math.random() * 26))
            ).join('');
            return prefix + suffix;
        });
        
        // 方案1
        const start1 = performance.now();
        LCPJS.longestCommonPrefixHorizontal(strs);
        const time1 = performance.now() - start1;
        result += `方案1 - 水平扫描法: ${time1.toFixed(2)}ms\n`;
        result += '时间复杂度: O(S)\n\n';
        
        // 方案2
        const start2 = performance.now();
        LCPJS.longestCommonPrefixVertical(strs);
        const time2 = performance.now() - start2;
        result += `方案2 - 垂直扫描法（推荐）: ${time2.toFixed(2)}ms\n`;
        result += '时间复杂度: O(S)\n\n';
        
        // 方案3
        const start3 = performance.now();
        LCPJS.longestCommonPrefixDivideConquer(strs);
        const time3 = performance.now() - start3;
        result += `方案3 - 分治法: ${time3.toFixed(2)}ms\n`;
        result += '时间复杂度: O(S)\n\n';
        
        // 方案4
        const start4 = performance.now();
        LCPJS.longestCommonPrefixBinarySearch(strs);
        const time4 = performance.now() - start4;
        result += `方案4 - 二分查找法: ${time4.toFixed(2)}ms\n`;
        result += '时间复杂度: O(S log m)\n\n';
        
        // 方案5
        const start5 = performance.now();
        LCPJS.longestCommonPrefixTrie(strs);
        const time5 = performance.now() - start5;
        result += `方案5 - 字典树法: ${time5.toFixed(2)}ms\n`;
        result += '时间复杂度: O(S)\n\n';
        
        result += '性能对比总结\n';
        result += '-'.repeat(70) + '\n';
        result += '最快方案: 垂直扫描法\n';
        result += '推荐方案: 垂直扫描法（综合考虑性能和实现复杂度）\n';
        
        return result;
    }
}

/**
 * 字典树节点
 */
class TrieNode {
    constructor() {
        this.children = {};
        this.count = 0;
    }
}

// 导出供Node.js使用
if (typeof module !== 'undefined' && module.exports) {
    module.exports = LCPJS;
}

JavaScript实现的详细说明

JavaScript版本的实现与Kotlin版本在逻辑上完全一致，但充分利用了JavaScript的语言特性。在水平扫描法中，我们使用了startsWith方法来检查前缀，这比手动比较字符更加简洁。在垂直扫描法中，我们使用了Math.min和map函数来找到最短字符串的长度。

在分治法中，我们使用了递归来实现分治思想。在二分查找法中，我们使用了Math.floor来计算中点。在字典树法中，我们使用了JavaScript对象来表示树的节点，这比使用类更加灵活。

JavaScript的performance.now()方法提供了微秒级的精度，使得性能测试更加准确。

ArkTS调用实现

完整的ArkTS代码实现

/**
 * 最长公共前缀(Longest Common Prefix)工具 - ArkTS版本（OpenHarmony鸿蒙）
 * 用于在鸿蒙应用中实现LCP算法
 */
import { webview } from '@kit.ArkWeb';
import { common } from '@kit.AbilityKit';

@Entry
@Component
struct LCPPage {
    @State inputStrings: string = 'flower,flow,flight';
    @State result: string = '';
    @State selectedMethod: string = '垂直扫描法';
    @State isLoading: boolean = false;
    @State performanceData: string = '';
    @State showPerformance: boolean = false;
    
    // Web视图控制器
    webviewController: webview.WebviewController = new webview.WebviewController();
    
    /**
     * 解析输入字符串
     */
    parseStrings(input: string): string[] {
        return input.split(',').map(s => s.trim()).filter(s => s.length > 0);
    }
    
    /**
     * 方案1：水平扫描法
     */
    longestCommonPrefixHorizontal(strs: string[]): string {
        if (strs.length === 0) return '';
        if (strs.length === 1) return strs[0];
        
        let prefix = strs[0];
        
        for (let i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(prefix)) {
                prefix = prefix.slice(0, -1);
                if (prefix === '') return '';
            }
        }
        
        return prefix;
    }
    
    /**
     * 方案2：垂直扫描法（推荐）
     */
    longestCommonPrefixVertical(strs: string[]): string {
        if (strs.length === 0) return '';
        
        const minLength = Math.min(...strs.map(s => s.length));
        
        for (let col = 0; col < minLength; col++) {
            const char = strs[0][col];
            
            for (let row = 1; row < strs.length; row++) {
                if (strs[row][col] !== char) {
                    return strs[0].substring(0, col);
                }
            }
        }
        
        return strs[0].substring(0, minLength);
    }
    
    /**
     * 方案3：分治法
     */
    longestCommonPrefixDivideConquer(strs: string[]): string {
        if (strs.length === 0) return '';
        return this.divideConquerHelper(strs, 0, strs.length - 1);
    }
    
    /**
     * 分治法辅助函数
     */
    divideConquerHelper(strs: string[], left: number, right: number): string {
        if (left === right) return strs[left];
        
        const mid = Math.floor((left + right) / 2);
        const leftLCP = this.divideConquerHelper(strs, left, mid);
        const rightLCP = this.divideConquerHelper(strs, mid + 1, right);
        
        return this.commonPrefix(leftLCP, rightLCP);
    }
    
    /**
     * 计算两个字符串的公共前缀
     */
    commonPrefix(str1: string, str2: string): string {
        const minLength = Math.min(str1.length, str2.length);
        
        for (let i = 0; i < minLength; i++) {
            if (str1[i] !== str2[i]) {
                return str1.substring(0, i);
            }
        }
        
        return str1.substring(0, minLength);
    }
    
    /**
     * 方案4：二分查找法
     */
    longestCommonPrefixBinarySearch(strs: string[]): string {
        if (strs.length === 0) return '';
        
        const minLength = Math.min(...strs.map(s => s.length));
        let left = 1;
        let right = minLength;
        
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            
            if (this.isCommonPrefix(strs, mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return strs[0].substring(0, right);
    }
    
    /**
     * 检查给定长度的前缀是否是所有字符串的公共前缀
     */
    isCommonPrefix(strs: string[], len: number): boolean {
        const prefix = strs[0].substring(0, len);
        
        for (let i = 1; i < strs.length; i++) {
            if (!strs[i].startsWith(prefix)) {
                return false;
            }
        }
        
        return true;
    }
    
    /**
     * 执行最长公共前缀计算
     */
    async executeLCP() {
        this.isLoading = true;
        this.showPerformance = false;
        
        try {
            const strs = this.parseStrings(this.inputStrings);
            
            if (strs.length === 0) {
                this.result = '错误：字符串不能为空';
                this.isLoading = false;
                return;
            }
            
            let lcp = '';
            
            switch (this.selectedMethod) {
                case '水平扫描法':
                    lcp = this.longestCommonPrefixHorizontal(strs);
                    break;
                case '垂直扫描法':
                    lcp = this.longestCommonPrefixVertical(strs);
                    break;
                case '分治法':
                    lcp = this.longestCommonPrefixDivideConquer(strs);
                    break;
                case '二分查找法':
                    lcp = this.longestCommonPrefixBinarySearch(strs);
                    break;
            }
            
            if (lcp === '') {
                this.result = '最长公共前缀: (空)';
            } else {
                this.result = `最长公共前缀: "${lcp}" (长度: ${lcp.length})`;
            }
        } catch (error) {
            this.result = '计算错误：' + error;
        }
        
        this.isLoading = false;
    }
    
    /**
     * 执行性能演示
     */
    async executePerformanceDemo() {
        this.isLoading = true;
        this.showPerformance = true;
        
        try {
            const count = 100;
            const length = 100;
            const strs = Array.from({ length: count }, () => {
                const prefix = 'common';
                const suffix = Array.from({ length: length - prefix.length }, () =>
                    String.fromCharCode(97 + Math.floor(Math.random() * 26))
                ).join('');
                return prefix + suffix;
            });
            
            let result = `最长公共前缀性能对比 (字符串数: ${count}, 长度: ${length})\n`;
            result += '='.repeat(70) + '\n\n';
            
            // 方案1
            const start1 = Date.now();
            this.longestCommonPrefixHorizontal(strs);
            const time1 = Date.now() - start1;
            result += `方案1 - 水平扫描法: ${time1}ms\n`;
            result += '时间复杂度: O(S)\n\n';
            
            // 方案2
            const start2 = Date.now();
            this.longestCommonPrefixVertical(strs);
            const time2 = Date.now() - start2;
            result += `方案2 - 垂直扫描法: ${time2}ms\n`;
            result += '时间复杂度: O(S)\n\n';
            
            // 方案3
            const start3 = Date.now();
            this.longestCommonPrefixDivideConquer(strs);
            const time3 = Date.now() - start3;
            result += `方案3 - 分治法: ${time3}ms\n`;
            result += '时间复杂度: O(S)\n\n';
            
            // 方案4
            const start4 = Date.now();
            this.longestCommonPrefixBinarySearch(strs);
            const time4 = Date.now() - start4;
            result += `方案4 - 二分查找法: ${time4}ms\n`;
            result += '时间复杂度: O(S log m)\n\n';
            
            result += '性能对比总结\n';
            result += '-'.repeat(70) + '\n';
            result += '最快方案: 垂直扫描法\n';
            result += '推荐方案: 垂直扫描法（综合考虑性能和实现复杂度）\n';
            
            this.performanceData = result;
        } catch (error) {
            this.performanceData = '演示失败：' + error;
        }
        
        this.isLoading = false;
    }
    
    build() {
        Column() {
            // 顶部栏
            Row() {
                Text('最长公共前缀(Longest Common Prefix)')
                    .fontSize(24)
                    .fontWeight(FontWeight.Bold)
                    .fontColor(Color.White)
            }
            .width('100%')
            .height(60)
            .backgroundColor('#1565C0')
            .justifyContent(FlexAlign.Center)
            
            // 主内容
            Scroll() {
                Column({ space: 16 }) {
                    // 输入字符串
                    Column() {
                        Text('输入字符串:')
                            .fontSize(14)
                            .fontWeight(FontWeight.Bold)
                            .width('100%')
                        
                        TextInput({ placeholder: '请输入字符串，用逗号分隔' })
                            .value(this.inputStrings)
                            .onChange((value: string) => {
                                this.inputStrings = value;
                            })
                            .width('100%')
                            .padding(8)
                            .backgroundColor(Color.White)
                            .borderRadius(4)
                    }
                    .width('100%')
                    .padding(12)
                    .backgroundColor('#E3F2FD')
                    .borderRadius(8)
                    
                    // 算法选择
                    Column() {
                        Text('选择算法:')
                            .fontSize(14)
                            .fontWeight(FontWeight.Bold)
                            .width('100%')
                        
                        Select([
                            { value: '水平扫描法' },
                            { value: '垂直扫描法' },
                            { value: '分治法' },
                            { value: '二分查找法' }
                        ])
                            .value(this.selectedMethod)
                            .onSelect((index: number, value: string) => {
                                this.selectedMethod = value;
                            })
                            .width('100%')
                    }
                    .width('100%')
                    .padding(12)
                    .backgroundColor('#E3F2FD')
                    .borderRadius(8)
                    
                    // 结果显示
                    if (this.result) {
                        Column() {
                            Text('计算结果:')
                                .fontSize(14)
                                .fontWeight(FontWeight.Bold)
                                .width('100%')
                            
                            Text(this.result)
                                .fontSize(12)
                                .width('100%')
                                .padding(8)
                                .backgroundColor('#F5F5F5')
                                .borderRadius(4)
                        }
                        .width('100%')
                        .padding(12)
                        .backgroundColor('#F5F5F5')
                        .borderRadius(8)
                    }
                    
                    // 性能数据显示
                    if (this.showPerformance && this.performanceData) {
                        Column() {
                            Text('性能对比:')
                                .fontSize(14)
                                .fontWeight(FontWeight.Bold)
                                .width('100%')
                            
                            Text(this.performanceData)
                                .fontSize(12)
                                .fontFamily('monospace')
                                .width('100%')
                                .padding(8)
                                .backgroundColor('#FFF3E0')
                                .borderRadius(4)
                        }
                        .width('100%')
                        .padding(12)
                        .backgroundColor('#FFF3E0')
                        .borderRadius(8)
                    }
                    
                    // 按钮组
                    Row({ space: 12 }) {
                        Button('执行计算')
                            .width('48%')
                            .onClick(() => this.executeLCP())
                            .enabled(!this.isLoading)
                        
                        Button('性能演示')
                            .width('48%')
                            .onClick(() => this.executePerformanceDemo())
                            .enabled(!this.isLoading)
                    }
                    .width('100%')
                    
                    // 加载指示器
                    if (this.isLoading) {
                        LoadingProgress()
                            .width(40)
                            .height(40)
                    }
                }
                .width('100%')
                .padding(16)
            }
            .layoutWeight(1)
        }
        .width('100%')
        .height('100%')
        .backgroundColor('#FAFAFA')
    }
}

ArkTS实现的详细说明

ArkTS版本为OpenHarmony鸿蒙平台提供了完整的用户界面。通过@State装饰器，我们可以管理应用的状态，当用户输入改变时，UI会自动更新。这个实现包含了输入字符串的输入框，以及算法选择的下拉菜单。

在计算结果的显示中，我们显示了最长公共前缀的内容和长度。这样用户可以直观地看到算法找到的最长公共前缀是什么。

性能演示功能允许用户在应用中直接看到不同算法的性能差异。通过对比100个字符串的情况，用户可以清楚地看到不同实现方式的性能表现。

应用场景分析

1. 自动完成系统

在搜索引擎和IDE的自动完成功能中，最长公共前缀用于快速过滤候选项。通过找到用户输入和候选项的最长公共前缀，系统可以高效地提供相关的建议。

2. 文件系统路径处理

在文件系统中，最长公共前缀可以用于找到一组文件的共同路径前缀。这对于批量操作和路径管理非常有用。

3. 域名和URL处理

在网络应用中，最长公共前缀可以用于处理域名和URL。例如，找到一组URL的共同前缀可以帮助识别相关的资源。

4. 版本控制系统

在版本控制系统中，最长公共前缀可以用于识别文件的共同部分，从而优化存储和比较。

5. 数据库查询优化

在数据库系统中，最长公共前缀可以用于优化索引和查询。通过找到查询条件的共同前缀，系统可以更高效地定位数据。

性能优化建议

1. 选择合适的算法

对于大多数实际应用，垂直扫描法是最优选择。它提供了O(S)的时间复杂度和O(1)的空间复杂度，这是理论上的最优复杂度。

2. 数据预处理

在处理大规模字符串时，可以先进行数据验证和排序。这可以减少实际需要处理的数据量，从而提高性能。

3. 缓存优化

对于需要多次查询的场景，可以使用字典树法来缓存结果，避免重复计算。

4. 并行处理

虽然LCP算法本身不易并行化，但在处理多个独立的LCP问题时，可以使用多线程或多进程来并行处理。

总结

最长公共前缀是一个经典的字符串处理问题，虽然问题陈述简单，但其解决方案涉及多种不同的算法思想。从水平扫描到垂直扫描，再到分治法、二分查找和字典树，每种方法都有其独特的优势。

通过在KMP框架下实现这个算法，我们可以在多个平台上使用同一套代码，提高开发效率。垂直扫描法是解决这个问题的最优方案，提供了O(S)的时间复杂度和O(1)的空间复杂度。在OpenHarmony鸿蒙平台上，我们可以通过ArkTS调用Kotlin编译的JavaScript代码，或者直接在ArkTS中实现算法，实现真正的跨平台开发。

掌握最长公共前缀问题的多种解决方案，不仅能够帮助开发者在面试中获得好成绩，更重要的是能够在实际项目中灵活应用这个经典算法，解决自动完成、路径处理等实际问题。

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net