本文详解如何将经典的 knuth-morris-pratt（kmp）字符串匹配算法封装为 laravel 可复用的服务类，包括目录结构、核心代码实现、自动加载配置及实际调用示例，助你高效集成于学术项目或生产应用中。
本文详解如何将经典的 knuth-morris-pratt（kmp）字符串匹配算法封装为 laravel 可复用的服务类，包括目录结构、核心代码实现、自动加载配置及实际调用示例，助你高效集成于学术项目或生产应用中。
在 Laravel 应用中集成 KMP 算法，关键在于遵循框架规范进行模块化封装，而非直接移植原始 PHP 脚本（如使用已废弃的 mysql_* 函数或全局变量）。Laravel 基于 PSR-4 自动加载标准，推荐将算法逻辑抽象为独立服务类，置于 app/Services 目录下，确保高内聚、低耦合与可测试性。
✅ 正确的目录结构与命名空间
首先，在 app/ 目录下创建 Services 文件夹，并新建 KMP.php：
mkdir -p app/Services touch app/Services/KMP.php
该文件需声明正确的命名空间 App\Services，并采用静态方法提供无状态的纯算法能力（不依赖请求、数据库或会话），符合 Laravel 的服务设计哲学。
✅ KMP 核心实现（优化版）
以下为适配 Laravel 9+ 的完整 KMP.php 实现，已修复原答案中潜在边界问题（如空模式处理），并增强健壮性与注释：
<?php
namespace App\Services;
class KMP
{
/**
* 在主串 $string 中查找所有子串 $pattern 的起始位置（0-based）
*
* @param string $string 主串（待搜索文本）
* @param string $pattern 模式串（关键词）
* @return array<int> 匹配位置索引数组，未找到时返回空数组
*/
public static function search(string $string, string $pattern): array
{
// 边界处理：空模式视为无效，空主串则无匹配
if ($pattern === '') {
return [];
}
if ($string === '') {
return [];
}
$M = strlen($pattern);
$N = strlen($string);
$retVal = [];
$i = 0; // 主串指针
$j = 0; // 模式串指针
$lps = [];
self::computeLPSArray($pattern, $M, $lps);
while ($i < $N) {
if ($pattern[$j] === $string[$i]) {
$i++;
$j++;
}
if ($j === $M) {
$retVal[] = $i - $j; // 记录匹配起始索引
$j = $lps[$j - 1];
} elseif ($i < $N && $pattern[$j] !== $string[$i]) {
if ($j !== 0) {
$j = $lps[$j - 1];
} else {
$i++;
}
}
}
return $retVal;
}
/**
* 构建最长相等前后缀（LPS）数组
*
* @param string $pattern 模式串
* @param int $m 模式串长度
* @param array &$lps 输出参数：LPS 数组
*/
private static function computeLPSArray(string $pattern, int $m, array &$lps): void
{
$len = 0;
$lps[0] = 0;
$i = 1;
while ($i < $m) {
if ($pattern[$i] === $pattern[$len]) {
$len++;
$lps[$i] = $len;
$i++;
} else {
if ($len !== 0) {
$len = $lps[$len - 1];
} else {
$lps[$i] = 0;
$i++;
}
}
}
}
}⚠️ 重要注意事项：
- *不要使用 `mysql_` 函数**：原示例代码已严重过时且存在 SQL 注入风险。Laravel 应统一通过 Eloquent 或 Query Builder 操作数据库。
- 避免在视图中执行算法：KMP 应在控制器或服务层调用，视图仅负责渲染结果。
- 输入校验不可省略：生产环境必须对用户输入（如搜索词）做 trim()、htmlspecialchars() 等过滤，防止 XSS。
- 性能提示：KMP 时间复杂度为 O(n+m)，适合长文本高频检索；若需全文模糊匹配，建议结合数据库 LIKE 或专用搜索引擎（如 Meilisearch）。
✅ 注册与调用方式
-
刷新自动加载（Laravel 会自动扫描 app/ 下 PSR-4 命名空间）：
composer dump-autoload
-
在路由或控制器中调用（以 routes/web.php 为例）：
<?php use Illuminate\Http\Request; use App\Services\KMP; Route::get('/kmp-search', function (Request $request) { $query = $request->input('q', ''); $content = "The quick brown fox jumps over the lazy dog. The fox is quick."; if (empty($query)) { return response()->json(['error' => 'Query is required'], 400); } $positions = KMP::search($content, $query); $count = count($positions); // 高亮显示（服务层不负责渲染，此处仅为演示） $highlighted = str_replace( $query, '<mark style="background-color: #ffeb3b;">' . htmlspecialchars($query) . '</mark>', htmlspecialchars($content) ); return response()->view('search.result', [ 'query' => $query, 'count' => $count, 'positions' => $positions, 'highlighted' => $highlighted, ]); }); -
在 Blade 模板中展示结果（resources/views/search/result.blade.php）：
<h2>Search Results for "{{ $query }}"</h2> <p>Found <strong>{{ $count }}</strong> occurrence(s) at positions: {{ implode(', ', $positions) }}</p> <div class="content">{!! $highlighted !!}</div>
✅ 总结
将 KMP 算法集成至 Laravel 并非简单“粘贴代码”，而是践行框架工程化思维：
? 使用 app/Services 封装无副作用的核心算法；
? 通过 PSR-4 自动加载实现零配置引入；
? 在控制器中协调数据流（接收请求 → 调用服务 → 渲染响应）；
? 始终坚持安全实践（输入过滤、输出转义、错误处理）。
此方案既满足课程设计中“实现至少一种算法”的硬性要求，也为后续扩展（如支持多关键词、正则预处理、缓存匹配结果）奠定坚实基础。
