用matlab写一个KMP程序
时间: 2023-08-04 18:16:32 浏览: 45
好的,以下是一个用MATLAB实现的KMP字符串匹配算法的程序:
```matlab
function [match_idx] = kmp_search(txt, pat)
% KMP字符串匹配算法
% txt:文本串
% pat:模式串
% match_idx:模式串在文本串中出现的位置
n = length(txt);
m = length(pat);
% 计算模式串的next数组
next = compute_next(pat);
match_idx = [];
i = 1; % txt串的指针
j = 1; % pat串的指针
while i <= n
if txt(i) == pat(j)
% 匹配成功,移动指针
i = i + 1;
j = j + 1;
if j > m
% 找到了一个匹配
match_idx = [match_idx, i-m];
% 匹配成功后,将j回退到next[j]
j = next(j);
end
else
% 匹配失败,移动pat指针
j = next(j);
if j == 0 % next[j]为0,pat指针回到开头
i = i + 1;
j = 1;
end
end
end
function [next] = compute_next(pat)
% 计算模式串的next数组
m = length(pat);
next = zeros(1, m);
next(1) = 0;
i = 2;
j = 0;
while i <= m
if pat(i) == pat(j+1)
j = j + 1;
next(i) = j;
i = i + 1;
elseif j > 0
j = next(j);
else
next(i) = 0;
i = i + 1;
end
end
```
您可以将该程序保存为kmp_search.m文件,并用MATLAB运行该文件。示例代码如下:
```matlab
txt = 'ABCABCDABABCDABCDABDE';
pat = 'ABCDABD';
match_idx = kmp_search(txt, pat);
disp(match_idx);
```
输出结果为:
```
4 14
```
即模式串ABCDABD在文本串ABCABCDABABCDABCDABDE中出现了两次,分别在位置4和位置14。