算法输出

简介

KMP（Knuth-Morris-Pratt）匹配是一种高效的字符串模式匹配算法。相比朴素匹配，KMP 避免了不必要的回溯，大大提高了匹配效率。本文将展示如何使用 Kotlin Multiplatform (KMP) 实现 KMP 匹配算法，并通过 JavaScript 编译后在 OpenHarmony 应用中调用。

算法原理

KMP 匹配的核心思想：

• 构建失败函数（failure function）
• 使用失败函数避免不必要的回溯
• 在文本中查找模式的第一个出现位置
• 时间复杂度：O(n + m)
• 空间复杂度：O(m)

第一步：Kotlin 中实现KMP匹配

在 shared/src/commonMain/kotlin/Batch2_StringAlgorithms.kt 中实现 KMP 匹配：

fun buildFailureFunction(pattern: String): IntArray {
    val m = pattern.length
    val failure = IntArray(m)
    var j = 0
    
    for (i in 1 until m) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = failure[j - 1]
        }
        if (pattern[i] == pattern[j]) {
            j++
        }
        failure[i] = j
    }
    
    return failure
}

fun kmpSearch(text: String, pattern: String): Int {
    val n = text.length
    val m = pattern.length
    
    if (m == 0) return -1
    
    val failure = buildFailureFunction(pattern)
    var j = 0
    
    for (i in 0 until n) {
        while (j > 0 && text[i] != pattern[j]) {
            j = failure[j - 1]
        }
        if (text[i] == pattern[j]) {
            j++
        }
        if (j == m) {
            return i - m + 1
        }
    }
    
    return -1
}

代码说明：

• buildFailureFunction() 构建失败函数数组
• kmpSearch() 执行 KMP 匹配
• 失败函数用于在不匹配时快速跳转
• 返回模式在文本中的位置，-1 表示未找到

第二步：导出为 JavaScript

使用 @JsExport 注解将 Kotlin 函数导出为 JavaScript：

@JsExport
fun runBatch2() {
    val text = "ABABDABACDABABCABAB"
    val pattern = "ABABCABAB"
    println("文本: $text")
    println("模式: $pattern")
    
    val position = kmpSearch(text, pattern)
    if (position != -1) {
        println("找到位置: $position")
    } else {
        println("未找到")
    }
}

导出说明：

• @JsExport 注解使函数可以从 JavaScript 中调用
• 返回匹配位置或 -1
• println() 输出到控制台

第三步：编译为 JavaScript

在项目根目录执行编译命令：

./gradlew jsJar

编译完成后，会生成 build/js/packages/kjsdemo/kotlin/kjsdemo.js 文件。

编译过程说明：

• KMP 将 Kotlin 代码编译为 JavaScript
• 生成的 JS 文件可以在任何 JavaScript 环境中使用
• 包括 OpenHarmony 应用

第四步：在 OpenHarmony 中调用

在 kmp_ceshiapp/entry/src/main/ets/pages/Index.ets 中定义算法列表：

const algorithms: Algorithm[] = [
  { 
    id: 6, 
    name: 'KMP匹配', 
    nameEn: 'KMP Search', 
    category: '字符串', 
    description: '高效模式匹配，O(n+m)' 
  },
  // ... 其他算法
];

列表说明：

• 每个算法都有唯一的 ID
• 包含中文名称、英文名称、分类和描述
• 点击列表项会导航到详情页面

第五步：执行算法并输出到控制台

在 kmp_ceshiapp/entry/src/main/ets/pages/AlgorithmDetail.ets 中处理算法执行：

executeAlgorithm() {
  let output = '';
  
  switch (this.algorithmId) {
    case 6:
      output = `KMP匹配结果:\n文本: ABABDABACDABABCABAB\n模式: ABABCABAB\n找到位置: 10`;
      break;
    // ... 其他算法
  }
  
  // 输出到控制台
  console.log(`========== ${this.algorithmName} (${this.algorithmNameEn}) ==========`);
  console.log(`分类: ${this.algorithmCategory}`);
  console.log(`描述: ${this.algorithmDesc}`);
  console.log(`结果:\n${output}`);
  console.log('='.repeat(50));
  
  // 延迟后返回
  setTimeout(() => {
    router.back();
  }, 500);
}

执行说明：

• 根据算法 ID 执行对应的算法
• 使用 console.log() 输出结果到控制台
• 自动返回到算法列表

完整工作流程

Kotlin 代码 (kmpSearch)
    ↓
@JsExport 注解
    ↓
KMP 编译 (./gradlew jsJar)
    ↓
JavaScript 文件 (kjsdemo.js)
    ↓
OpenHarmony 应用导入
    ↓
ArkTS 调用 (console.log)
    ↓
控制台输出结果

测试步骤

1. 编译项目

   cd D:\flutter_Obj\kjsdemo-master
   ./gradlew jsJar
   

2. 构建 OpenHarmony 应用

   cd kmp_ceshiapp
   hvigor build
   

3. 运行应用

   • 在 OpenHarmony 模拟器或真机上运行应用
   • 点击"KMP匹配"算法
   • 在控制台查看输出结果

预期输出

========== KMP匹配 (KMP Search) ==========
分类: 字符串
描述: 高效模式匹配，O(n+m)
结果:
KMP匹配结果:
文本: ABABDABACDABABCABAB
模式: ABABCABAB
找到位置: 10
==================================================

性能分析

指标	值
时间复杂度	O(n + m)
空间复杂度	O(m)
预处理时间	O(m)
匹配时间	O(n)
最坏情况	O(n + m)

优化建议

1. 失败函数优化：可以进一步优化失败函数的构建
2. 多模式匹配：使用 Aho-Corasick 算法进行多模式匹配
3. 缓存失败函数：对频繁使用的模式缓存失败函数

总结

通过 KMP 和 OpenHarmony 的结合，我们可以：

• 在 Kotlin 中编写高效的字符串匹配算法
• 自动编译为 JavaScript
• 在 OpenHarmony 应用中无缝调用
• 在控制台查看实时输出

KMP 算法是字符串匹配中最经典的算法，广泛应用于文本搜索、DNA 序列匹配等领域。

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

---