数据结构：KMP模式匹配算法(基于MATLAB)

function KMP(T, P)

%%KMP：此算法是一种改进的字符串匹配算法

%输入：

%     T--原字符串

%     P--模式

%输出：

%     返回所有匹配字符串第一个字符的下标

n = length(T);

m = length(P);

pi=Compute_Prefix(P);

q = 0;                                

for i = 1:n                            

   while ( (q > 0) && (P(q+1) ~=T(i) ))

       q = pi(q);                    

   end

   if P(q+1)==T(i)

       q = q + 1;                    

   end

   if q == m                        

       temp = i - m ;

       fprintf('Pattern occurs with shift%u.\n' ,temp);

       q = pi(q);                    

   end

end

%------------- 以下是子函数　-----------

function pi =Compute_Prefix(P)

%%KMP函数的子函数

m = length(P);

pi(1)=0;

k = 0;

for q = 2:m

   while ( (k>0) && (P(k+1) ~= P(q)))

       k = pi(k);

   end

   if P(k+1) == P(q)

       k=k+1;

   end

   pi(q)=k;

end

%------------- 测试(用法)------------

>> t='thisis a kmp string matching test string';

>>p='string';

>> KMP(t,p);

Pattern occurswith shift 14.

Pattern occurswith shift 35.