文章概述

最长公共子序列（Longest Common Subsequence, LCS）是计算机科学中最重要的算法问题之一，也是动态规划领域的经典之作。与最长递增子序列(LIS)不同，LCS处理的是两个序列之间的关系，找到它们共有的最长子序列。这个问题在实际应用中无处不在：从文本比较和版本控制系统，到DNA序列分析和数据去重，LCS算法都扮演着关键角色。

LCS问题的核心难点在于需要同时考虑两个序列的特性，这使得问题的复杂度相对较高。然而，通过巧妙的动态规划设计和各种优化技巧，我们可以将时间复杂度从O(n²m²)降低到O(nm)，甚至在某些特殊情况下进一步优化。

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

算法原理详解

问题定义

给定两个字符串或数组，找到它们的最长公共子序列。子序列是指从原序列中删除零个或多个元素后得到的序列，但保持原有元素的相对顺序。

例如：

• 输入：str1 = "abcde", str2 = "ace"
• 输出：3（最长公共子序列为 "ace"）

另一个例子：

• 输入：str1 = "abc", str2 = "abc"
• 输出：3（最长公共子序列为 "abc"）

解决方案对比

方案1：二维动态规划法（2D DP）

这是最经典的LCS解决方案。定义dp[i][j]为str1[0...i-1]和str2[0...j-1]的最长公共子序列长度。递推关系为：

• 如果str1[i-1] == str2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1
• 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

时间复杂度：O(nm)
空间复杂度：O(nm)
优点：易于理解，易于扩展，可以回溯得到具体子序列
缺点：空间复杂度较高
适用场景：需要具体子序列的场景

方案2：空间优化的动态规划法（Space Optimized DP）

通过观察可以发现，计算dp[i][j]只需要dp[i-1][j]和dp[i][j-1]，因此我们可以只保留两行数据，将空间复杂度降低到O(min(n, m))。

时间复杂度：O(nm)
空间复杂度：O(min(n, m))
优点：空间效率高，适合大规模数据
缺点：无法直接回溯得到具体子序列
适用场景：内存受限的场景

方案3：递归+记忆化法（Memoization）

使用递归的方式实现LCS，并使用哈希表或二维数组缓存已计算的结果。这种方法的优点是代码更加直观，易于理解递推关系。

时间复杂度：O(nm)
空间复杂度：O(nm)
优点：代码直观，易于理解
缺点：递归调用开销较大
适用场景：教学和理解算法原理

方案4：路径回溯法（Path Reconstruction）

在计算LCS长度的基础上，通过额外的方向数组来记录递推的方向，从而能够回溯出具体的LCS子序列。

时间复杂度：O(nm)
空间复杂度：O(nm)
优点：可以得到具体的LCS子序列
缺点：需要额外的空间和回溯逻辑
适用场景：需要具体子序列的所有场景

算法选择指南

• 只需要LCS长度且内存充足：使用2D DP法
• 只需要LCS长度且内存受限：使用空间优化DP法
• 需要理解算法原理：使用递归+记忆化法
• 需要具体的LCS子序列：使用路径回溯法

Kotlin实现

完整的Kotlin代码实现

/**
 * 最长公共子序列(LCS)算法工具类 - KMP OpenHarmony
 * 提供多种解决方案来求解最长公共子序列
 */
object LCSUtils {
    
    /**
     * 方案1：二维动态规划法
     * 时间复杂度：O(nm)
     * 空间复杂度：O(nm)
     * 
     * 原理：
     * dp[i][j] 表示 str1[0...i-1] 和 str2[0...j-1] 的LCS长度
     * 如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
     * 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
     */
    fun lcs2DDP(str1: String, str2: String): Int {
        val m = str1.length
        val n = str2.length
        val dp = Array(m + 1) { IntArray(n + 1) }
        
        for (i in 1..m) {
            for (j in 1..n) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1
                } else {
                    dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])
                }
            }
        }
        
        return dp[m][n]
    }
    
    /**
     * 方案2：空间优化的动态规划法
     * 时间复杂度：O(nm)
     * 空间复杂度：O(min(n, m))
     * 
     * 原理：
     * 只保留两行数据，不断更新当前行
     * 这样可以将空间复杂度从O(nm)降低到O(min(n, m))
     */
    fun lcsSpaceOptimized(str1: String, str2: String): Int {
        val m = str1.length
        val n = str2.length
        
        // 确保str1是较短的字符串
        val (s1, s2) = if (m <= n) Pair(str1, str2) else Pair(str2, str1)
        val len1 = s1.length
        val len2 = s2.length
        
        var prev = IntArray(len1 + 1)
        var curr = IntArray(len1 + 1)
        
        for (j in 1..len2) {
            for (i in 1..len1) {
                if (s1[i - 1] == s2[j - 1]) {
                    curr[i] = prev[i - 1] + 1
                } else {
                    curr[i] = maxOf(prev[i], curr[i - 1])
                }
            }
            
            val temp = prev
            prev = curr
            curr = temp
        }
        
        return prev[len1]
    }
    
    /**
     * 方案3：递归+记忆化法
     * 时间复杂度：O(nm)
     * 空间复杂度：O(nm)
     */
    fun lcsMemoization(str1: String, str2: String): Int {
        val memo = mutableMapOf<Pair<Int, Int>, Int>()
        
        fun helper(i: Int, j: Int): Int {
            if (i == 0 || j == 0) return 0
            
            val key = Pair(i, j)
            if (key in memo) return memo[key]!!
            
            val result = if (str1[i - 1] == str2[j - 1]) {
                helper(i - 1, j - 1) + 1
            } else {
                maxOf(helper(i - 1, j), helper(i, j - 1))
            }
            
            memo[key] = result
            return result
        }
        
        return helper(str1.length, str2.length)
    }
    
    /**
     * 方案4：路径回溯法 - 返回具体的LCS
     * 时间复杂度：O(nm)
     * 空间复杂度：O(nm)
     */
    fun lcsWithPath(str1: String, str2: String): String {
        val m = str1.length
        val n = str2.length
        val dp = Array(m + 1) { IntArray(n + 1) }
        
        // 构建DP表
        for (i in 1..m) {
            for (j in 1..n) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1
                } else {
                    dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])
                }
            }
        }
        
        // 回溯构建LCS
        val result = StringBuilder()
        var i = m
        var j = n
        
        while (i > 0 && j > 0) {
            when {
                str1[i - 1] == str2[j - 1] -> {
                    result.insert(0, str1[i - 1])
                    i--
                    j--
                }
                dp[i - 1][j] > dp[i][j - 1] -> {
                    i--
                }
                else -> {
                    j--
                }
            }
        }
        
        return result.toString()
    }
    
    /**
     * 方案5：获取所有LCS
     * 时间复杂度：O(nm)
     * 空间复杂度：O(nm)
     */
    fun lcsAll(str1: String, str2: String): Set<String> {
        val m = str1.length
        val n = str2.length
        val dp = Array(m + 1) { IntArray(n + 1) }
        
        // 构建DP表
        for (i in 1..m) {
            for (j in 1..n) {
                if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1
                } else {
                    dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])
                }
            }
        }
        
        // 回溯获取所有LCS
        val result = mutableSetOf<String>()
        
        fun backtrack(i: Int, j: Int, path: String) {
            if (i == 0 || j == 0) {
                if (path.length == dp[m][n]) {
                    result.add(path)
                }
                return
            }
            
            if (str1[i - 1] == str2[j - 1]) {
                backtrack(i - 1, j - 1, str1[i - 1] + path)
            } else {
                if (dp[i - 1][j] >= dp[i][j - 1]) {
                    backtrack(i - 1, j, path)
                }
                if (dp[i][j - 1] >= dp[i - 1][j]) {
                    backtrack(i, j - 1, path)
                }
            }
        }
        
        backtrack(m, n, "")
        return result
    }
    
    /**
     * 性能演示函数 - 对比多种方法的性能
     */
    fun performanceDemo(size: Int = 100): String {
        val result = StringBuilder()
        result.append("最长公共子序列(LCS)性能对比 (字符串长度: $size)\n")
        result.append("=".repeat(70)).append("\n\n")
        
        // 生成测试数据
        val str1 = (0 until size).map { (Math.random() * 26).toInt().toChar() }.joinToString("")
        val str2 = (0 until size).map { (Math.random() * 26).toInt().toChar() }.joinToString("")
        
        // 方案1：2D DP
        val time1 = measureTimeMillis {
            lcs2DDP(str1, str2)
        }
        result.append("方案1 - 二维动态规划法\n")
        result.append("耗时: ${time1}ms\n")
        result.append("时间复杂度: O(nm)\n")
        result.append("空间复杂度: O(nm)\n\n")
        
        // 方案2：空间优化DP
        val time2 = measureTimeMillis {
            lcsSpaceOptimized(str1, str2)
        }
        result.append("方案2 - 空间优化动态规划法\n")
        result.append("耗时: ${time2}ms\n")
        result.append("时间复杂度: O(nm)\n")
        result.append("空间复杂度: O(min(n, m))\n\n")
        
        // 方案3：记忆化
        val time3 = measureTimeMillis {
            lcsMemoization(str1, str2)
        }
        result.append("方案3 - 递归+记忆化法\n")
        result.append("耗时: ${time3}ms\n")
        result.append("时间复杂度: O(nm)\n")
        result.append("空间复杂度: O(nm)\n\n")
        
        // 方案4：路径回溯
        val time4 = measureTimeMillis {
            lcsWithPath(str1, str2)
        }
        result.append("方案4 - 路径回溯法（推荐）\n")
        result.append("耗时: ${time4}ms\n")
        result.append("时间复杂度: O(nm)\n")
        result.append("空间复杂度: O(nm)\n\n")
        
        // 性能对比
        result.append("性能对比总结\n")
        result.append("-".repeat(70)).append("\n")
        result.append("最快方案: 空间优化动态规划法\n")
        result.append("推荐方案: 路径回溯法（可获得具体LCS）\n")
        
        return result.toString()
    }
}

// 扩展函数
fun Pair<String, String>.findLCS(): Int {
    return LCSUtils.lcs2DDP(this.first, this.second)
}

// 使用示例
fun main() {
    println("KMP OpenHarmony 最长公共子序列(LCS)算法演示\n")
    
    val str1 = "abcde"
    val str2 = "ace"
    
    println("字符串1: $str1")
    println("字符串2: $str2\n")
    
    // 方案1
    val result1 = LCSUtils.lcs2DDP(str1, str2)
    println("方案1 - 二维DP法: $result1")
    
    // 方案2
    val result2 = LCSUtils.lcsSpaceOptimized(str1, str2)
    println("方案2 - 空间优化法: $result2")
    
    // 方案3
    val result3 = LCSUtils.lcsMemoization(str1, str2)
    println("方案3 - 记忆化法: $result3")
    
    // 方案4
    val result4 = LCSUtils.lcsWithPath(str1, str2)
    println("方案4 - 路径回溯法: $result4")
    
    println("\n性能演示:")
    println(LCSUtils.performanceDemo(100))
}

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

Kotlin实现的详细说明

Kotlin实现提供了五种不同的LCS解决方案。二维动态规划法是最经典的方法，通过构建一个二维表格来记录所有子问题的解。这种方法易于理解，也易于扩展以获取具体的LCS子序列。

空间优化的动态规划法通过观察到只需要前一行的数据这一特点，将空间复杂度从O(nm)降低到O(min(n, m))。这对于处理大规模字符串非常重要，可以显著减少内存占用。

递归+记忆化法提供了另一种思考方式，通过递归地定义子问题，然后使用哈希表缓存结果。这种方法的代码更加直观，易于理解递推关系。

路径回溯法在计算LCS长度的基础上，通过回溯DP表来重构具体的LCS子序列。这对于需要知道具体匹配内容的应用场景非常重要。

获取所有LCS的方法展示了如何在有多个LCS时，找到所有可能的结果。这在某些应用中很有用，例如文本比较工具可能需要显示所有可能的匹配。

JavaScript实现

完整的JavaScript代码实现

/**
 * 最长公共子序列(LCS)算法工具类 - JavaScript版本
 * 用于在Web和Node.js环境中使用
 */
class LCSJS {
    /**
     * 方案1：二维动态规划法
     * @param {string} str1 - 第一个字符串
     * @param {string} str2 - 第二个字符串
     * @returns {number} LCS长度
     */
    static lcs2DDP(str1, str2) {
        const m = str1.length;
        const n = str2.length;
        const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
        
        for (let i = 1; i <= m; i++) {
            for (let j = 1; j <= n; j++) {
                if (str1[i - 1] === str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[m][n];
    }
    
    /**
     * 方案2：空间优化的动态规划法
     * @param {string} str1 - 第一个字符串
     * @param {string} str2 - 第二个字符串
     * @returns {number} LCS长度
     */
    static lcsSpaceOptimized(str1, str2) {
        const [s1, s2] = str1.length <= str2.length ? [str1, str2] : [str2, str1];
        const len1 = s1.length;
        const len2 = s2.length;
        
        let prev = new Array(len1 + 1).fill(0);
        let curr = new Array(len1 + 1).fill(0);
        
        for (let j = 1; j <= len2; j++) {
            for (let i = 1; i <= len1; i++) {
                if (s1[i - 1] === s2[j - 1]) {
                    curr[i] = prev[i - 1] + 1;
                } else {
                    curr[i] = Math.max(prev[i], curr[i - 1]);
                }
            }
            
            [prev, curr] = [curr, prev];
        }
        
        return prev[len1];
    }
    
    /**
     * 方案3：递归+记忆化法
     * @param {string} str1 - 第一个字符串
     * @param {string} str2 - 第二个字符串
     * @returns {number} LCS长度
     */
    static lcsMemoization(str1, str2) {
        const memo = new Map();
        
        const helper = (i, j) => {
            if (i === 0 || j === 0) return 0;
            
            const key = `${i},${j}`;
            if (memo.has(key)) return memo.get(key);
            
            let result;
            if (str1[i - 1] === str2[j - 1]) {
                result = helper(i - 1, j - 1) + 1;
            } else {
                result = Math.max(helper(i - 1, j), helper(i, j - 1));
            }
            
            memo.set(key, result);
            return result;
        };
        
        return helper(str1.length, str2.length);
    }
    
    /**
     * 方案4：路径回溯法 - 返回具体的LCS
     * @param {string} str1 - 第一个字符串
     * @param {string} str2 - 第二个字符串
     * @returns {string} LCS子序列
     */
    static lcsWithPath(str1, str2) {
        const m = str1.length;
        const n = str2.length;
        const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
        
        // 构建DP表
        for (let i = 1; i <= m; i++) {
            for (let j = 1; j <= n; j++) {
                if (str1[i - 1] === str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 回溯构建LCS
        let result = '';
        let i = m;
        let j = n;
        
        while (i > 0 && j > 0) {
            if (str1[i - 1] === str2[j - 1]) {
                result = str1[i - 1] + result;
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        
        return result;
    }
    
    /**
     * 方案5：获取所有LCS
     * @param {string} str1 - 第一个字符串
     * @param {string} str2 - 第二个字符串
     * @returns {Set<string>} 所有LCS子序列
     */
    static lcsAll(str1, str2) {
        const m = str1.length;
        const n = str2.length;
        const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
        
        // 构建DP表
        for (let i = 1; i <= m; i++) {
            for (let j = 1; j <= n; j++) {
                if (str1[i - 1] === str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 回溯获取所有LCS
        const result = new Set();
        
        const backtrack = (i, j, path) => {
            if (i === 0 || j === 0) {
                if (path.length === dp[m][n]) {
                    result.add(path);
                }
                return;
            }
            
            if (str1[i - 1] === str2[j - 1]) {
                backtrack(i - 1, j - 1, str1[i - 1] + path);
            } else {
                if (dp[i - 1][j] >= dp[i][j - 1]) {
                    backtrack(i - 1, j, path);
                }
                if (dp[i][j - 1] >= dp[i - 1][j]) {
                    backtrack(i, j - 1, path);
                }
            }
        };
        
        backtrack(m, n, '');
        return result;
    }
    
    /**
     * 性能演示函数
     * @param {number} size - 字符串长度
     * @returns {string} 性能报告
     */
    static performanceDemo(size = 100) {
        let result = `最长公共子序列(LCS)性能对比 (字符串长度: ${size})\n`;
        result += '='.repeat(70) + '\n\n';
        
        // 生成测试数据
        const str1 = Array.from({ length: size }, () => 
            String.fromCharCode(97 + Math.floor(Math.random() * 26))
        ).join('');
        const str2 = Array.from({ length: size }, () => 
            String.fromCharCode(97 + Math.floor(Math.random() * 26))
        ).join('');
        
        // 方案1
        const start1 = performance.now();
        LCSJS.lcs2DDP(str1, str2);
        const time1 = performance.now() - start1;
        result += `方案1 - 二维动态规划法: ${time1.toFixed(2)}ms\n`;
        result += '时间复杂度: O(nm)\n\n';
        
        // 方案2
        const start2 = performance.now();
        LCSJS.lcsSpaceOptimized(str1, str2);
        const time2 = performance.now() - start2;
        result += `方案2 - 空间优化动态规划法: ${time2.toFixed(2)}ms\n`;
        result += '时间复杂度: O(nm)\n\n';
        
        // 方案3
        const start3 = performance.now();
        LCSJS.lcsMemoization(str1, str2);
        const time3 = performance.now() - start3;
        result += `方案3 - 递归+记忆化法: ${time3.toFixed(2)}ms\n`;
        result += '时间复杂度: O(nm)\n\n';
        
        // 方案4
        const start4 = performance.now();
        LCSJS.lcsWithPath(str1, str2);
        const time4 = performance.now() - start4;
        result += `方案4 - 路径回溯法（推荐）: ${time4.toFixed(2)}ms\n`;
        result += '时间复杂度: O(nm)\n\n';
        
        result += '性能对比总结\n';
        result += '-'.repeat(70) + '\n';
        result += '最快方案: 空间优化动态规划法\n';
        result += '推荐方案: 路径回溯法（可获得具体LCS）\n';
        
        return result;
    }
}

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

JavaScript实现的详细说明

JavaScript版本的实现与Kotlin版本在逻辑上完全一致，但充分利用了JavaScript的语言特性。在二维DP实现中，我们使用了Array.fill().map()的组合来创建二维数组，这是JavaScript中创建二维数组的常见方式。

在空间优化版本中，我们使用了解构赋值[prev, curr] = [curr, prev]来交换两行数据，这比传统的临时变量交换更加简洁。在记忆化实现中，我们使用了JavaScript的Map对象而不是普通对象，因为Map对象在处理复杂键时性能更好。

JavaScript的performance.now()方法提供了微秒级的精度，使得性能测试更加准确。在lcsAll方法中，我们使用了Set来存储所有可能的LCS，避免重复。

ArkTS调用实现

完整的ArkTS代码实现

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

@Entry
@Component
struct LCSPage {
    @State str1: string = 'abcde';
    @State str2: string = 'ace';
    @State result: string = '';
    @State selectedMethod: string = '路径回溯法';
    @State isLoading: boolean = false;
    @State lcsSequence: string = '';
    @State performanceData: string = '';
    @State showPerformance: boolean = false;
    
    // Web视图控制器
    webviewController: webview.WebviewController = new webview.WebviewController();
    
    /**
     * 方案1：二维动态规划法
     */
    lcs2DDP(str1: string, str2: string): number {
        const m = str1.length;
        const n = str2.length;
        const dp: number[][] = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
        
        for (let i = 1; i <= m; i++) {
            for (let j = 1; j <= n; j++) {
                if (str1[i - 1] === str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[m][n];
    }
    
    /**
     * 方案2：空间优化的动态规划法
     */
    lcsSpaceOptimized(str1: string, str2: string): number {
        const [s1, s2] = str1.length <= str2.length ? [str1, str2] : [str2, str1];
        const len1 = s1.length;
        const len2 = s2.length;
        
        let prev = new Array(len1 + 1).fill(0);
        let curr = new Array(len1 + 1).fill(0);
        
        for (let j = 1; j <= len2; j++) {
            for (let i = 1; i <= len1; i++) {
                if (s1[i - 1] === s2[j - 1]) {
                    curr[i] = prev[i - 1] + 1;
                } else {
                    curr[i] = Math.max(prev[i], curr[i - 1]);
                }
            }
            
            [prev, curr] = [curr, prev];
        }
        
        return prev[len1];
    }
    
    /**
     * 方案3：递归+记忆化法
     */
    lcsMemoization(str1: string, str2: string): number {
        const memo = new Map<string, number>();
        
        const helper = (i: number, j: number): number => {
            if (i === 0 || j === 0) return 0;
            
            const key = `${i},${j}`;
            if (memo.has(key)) return memo.get(key)!;
            
            let result: number;
            if (str1[i - 1] === str2[j - 1]) {
                result = helper(i - 1, j - 1) + 1;
            } else {
                result = Math.max(helper(i - 1, j), helper(i, j - 1));
            }
            
            memo.set(key, result);
            return result;
        };
        
        return helper(str1.length, str2.length);
    }
    
    /**
     * 方案4：路径回溯法 - 返回具体的LCS
     */
    lcsWithPath(str1: string, str2: string): string {
        const m = str1.length;
        const n = str2.length;
        const dp: number[][] = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
        
        // 构建DP表
        for (let i = 1; i <= m; i++) {
            for (let j = 1; j <= n; j++) {
                if (str1[i - 1] === str2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 回溯构建LCS
        let result = '';
        let i = m;
        let j = n;
        
        while (i > 0 && j > 0) {
            if (str1[i - 1] === str2[j - 1]) {
                result = str1[i - 1] + result;
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        
        return result;
    }
    
    /**
     * 执行LCS计算
     */
    async executeLCS() {
        this.isLoading = true;
        this.showPerformance = false;
        
        try {
            if (this.str1.length === 0 || this.str2.length === 0) {
                this.result = '错误：字符串不能为空';
                this.isLoading = false;
                return;
            }
            
            let lcsLength = 0;
            
            switch (this.selectedMethod) {
                case '二维动态规划法':
                    lcsLength = this.lcs2DDP(this.str1, this.str2);
                    break;
                case '空间优化法':
                    lcsLength = this.lcsSpaceOptimized(this.str1, this.str2);
                    break;
                case '路径回溯法':
                    const lcs = this.lcsWithPath(this.str1, this.str2);
                    lcsLength = lcs.length;
                    this.lcsSequence = `LCS子序列: "${lcs}"`;
                    break;
            }
            
            this.result = `最长公共子序列长度: ${lcsLength}`;
        } catch (error) {
            this.result = '计算错误：' + error;
        }
        
        this.isLoading = false;
    }
    
    /**
     * 执行性能演示
     */
    async executePerformanceDemo() {
        this.isLoading = true;
        this.showPerformance = true;
        
        try {
            const size = 100;
            const str1 = Array.from({ length: size }, () => 
                String.fromCharCode(97 + Math.floor(Math.random() * 26))
            ).join('');
            const str2 = Array.from({ length: size }, () => 
                String.fromCharCode(97 + Math.floor(Math.random() * 26))
            ).join('');
            
            let result = `最长公共子序列(LCS)性能对比 (字符串长度: ${size})\n`;
            result += '='.repeat(70) + '\n\n';
            
            // 方案1
            const start1 = Date.now();
            this.lcs2DDP(str1, str2);
            const time1 = Date.now() - start1;
            result += `方案1 - 二维动态规划法: ${time1}ms\n`;
            result += '时间复杂度: O(nm)\n\n';
            
            // 方案2
            const start2 = Date.now();
            this.lcsSpaceOptimized(str1, str2);
            const time2 = Date.now() - start2;
            result += `方案2 - 空间优化动态规划法: ${time2}ms\n`;
            result += '时间复杂度: O(nm)\n\n';
            
            // 方案3
            const start3 = Date.now();
            this.lcsMemoization(str1, str2);
            const time3 = Date.now() - start3;
            result += `方案3 - 递归+记忆化法: ${time3}ms\n`;
            result += '时间复杂度: O(nm)\n\n';
            
            // 方案4
            const start4 = Date.now();
            this.lcsWithPath(str1, str2);
            const time4 = Date.now() - start4;
            result += `方案4 - 路径回溯法: ${time4}ms\n`;
            result += '时间复杂度: O(nm)\n\n';
            
            result += '性能对比总结\n';
            result += '-'.repeat(70) + '\n';
            result += '最快方案: 空间优化动态规划法\n';
            result += '推荐方案: 路径回溯法（可获得具体LCS）\n';
            
            this.performanceData = result;
        } catch (error) {
            this.performanceData = '演示失败：' + error;
        }
        
        this.isLoading = false;
    }
    
    build() {
        Column() {
            // 顶部栏
            Row() {
                Text('最长公共子序列(LCS)')
                    .fontSize(24)
                    .fontWeight(FontWeight.Bold)
                    .fontColor(Color.White)
            }
            .width('100%')
            .height(60)
            .backgroundColor('#1565C0')
            .justifyContent(FlexAlign.Center)
            
            // 主内容
            Scroll() {
                Column({ space: 16 }) {
                    // 字符串1输入
                    Column() {
                        Text('字符串1:')
                            .fontSize(14)
                            .fontWeight(FontWeight.Bold)
                            .width('100%')
                        
                        TextInput({ placeholder: '请输入第一个字符串' })
                            .value(this.str1)
                            .onChange((value: string) => {
                                this.str1 = value;
                            })
                            .width('100%')
                            .padding(8)
                            .backgroundColor(Color.White)
                            .borderRadius(4)
                    }
                    .width('100%')
                    .padding(12)
                    .backgroundColor('#E3F2FD')
                    .borderRadius(8)
                    
                    // 字符串2输入
                    Column() {
                        Text('字符串2:')
                            .fontSize(14)
                            .fontWeight(FontWeight.Bold)
                            .width('100%')
                        
                        TextInput({ placeholder: '请输入第二个字符串' })
                            .value(this.str2)
                            .onChange((value: string) => {
                                this.str2 = 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(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)
                    }
                    
                    // LCS子序列显示
                    if (this.lcsSequence) {
                        Column() {
                            Text('LCS子序列:')
                                .fontSize(14)
                                .fontWeight(FontWeight.Bold)
                                .width('100%')
                            
                            Text(this.lcsSequence)
                                .fontSize(12)
                                .width('100%')
                                .padding(8)
                                .backgroundColor('#E8F5E9')
                                .borderRadius(4)
                        }
                        .width('100%')
                        .padding(12)
                        .backgroundColor('#E8F5E9')
                        .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.executeLCS())
                            .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会自动更新。这个实现包含了两个字符串的输入框，以及算法选择的下拉菜单。

在计算结果的显示中，我们不仅显示了LCS的长度，还显示了具体的LCS子序列（当选择路径回溯法时）。这样用户可以直观地看到算法找到的最长公共子序列是什么。

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

应用场景分析

1. 文本比较和差异检测

在文本编辑器和版本控制系统中，LCS用于比较两个文本文件的差异。通过找到LCS，系统可以高效地计算出哪些行被添加、删除或修改。这是Git和其他版本控制系统的核心算法。

2. DNA序列分析

在生物信息学中，LCS用于比对DNA序列。通过找到两个DNA序列的LCS，科学家可以识别出共同的基因片段，理解不同物种之间的进化关系。这对于医学研究和遗传学研究非常重要。

3. 数据去重和匹配

在数据库系统和数据清洗中，LCS用于识别重复或相似的记录。通过计算LCS，系统可以判断两条记录的相似程度，从而进行去重或合并操作。

4. 拼写检查和纠正

在拼写检查工具中，LCS用于找到用户输入的单词与字典中单词的最长公共子序列，从而提供更准确的纠正建议。

5. 推荐系统

在推荐系统中，LCS用于比较用户的行为序列和其他用户的行为序列，找到共同的兴趣模式，从而提供更准确的推荐。

性能优化建议

1. 选择合适的算法

对于只需要LCS长度的场景，使用空间优化的动态规划法可以显著减少内存占用。对于需要具体LCS的场景，使用路径回溯法是最佳选择。对于理解算法原理，使用递归+记忆化法最为直观。

2. 数据预处理

在处理大规模字符串时，可以先进行预处理，例如移除空格、转换大小写等，以减少实际需要比较的字符数。

3. 早期终止

如果在计算过程中发现LCS长度已经不可能超过某个阈值，可以提前终止计算，从而提高性能。

4. 并行处理

虽然LCS算法本身不易并行化，但在处理多个字符串对的LCS时，可以使用多线程或多进程来并行处理。

总结

最长公共子序列是一个经典的动态规划问题，虽然问题陈述简单，但其解决方案涉及多种不同的算法思想。从基础的二维DP到空间优化的版本，再到递归+记忆化和路径回溯，每种方法都有其独特的优势。

通过在KMP框架下实现这个算法，我们可以在多个平台上使用同一套代码，提高开发效率。路径回溯法是解决需要具体LCS的问题的最优方案，而空间优化法则是在内存受限情况下的最佳选择。

在OpenHarmony鸿蒙平台上，我们可以通过ArkTS调用Kotlin编译的JavaScript代码，或者直接在ArkTS中实现算法，实现真正的跨平台开发。掌握LCS算法的多种解决方案，不仅能够帮助开发者在面试中获得好成绩，更重要的是能够在实际项目中灵活应用这个经典算法，解决文本比较、序列分析等实际问题。欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net