kmp算法matlab实现

以下是 KMP 算法的 MATLAB 代码实现：

function KMPSearch(pat, txt)
    M = length(pat);
    N = length(txt);

    lps = zeros(1, M);
    lps = computeLPSArray(pat, M, lps);

    i = 1; 
    j = 1;  
    while (i <= N) 
        if (pat(j) == txt(i))
            j = j + 1;
            i = i + 1;
        end

        if (j == M + 1)
            fprintf('Found pattern at index %d \n', i - j);
            j = lps(j - 1);
        end

        if (i <= N && pat(j) ~= txt(i))
            if (j ~= 1)
                j = lps(j - 1);
            else
                i = i + 1;
            end
        end
    end
end

function lps = computeLPSArray(pat, M, lps)
    len = 0;

    lps(1) = 0;

    i = 2;
    while (i <= M) 
        if (pat(i) == pat(len + 1))
            len = len + 1;
            lps(i) = len;
            i = i + 1;
        else 
            if (len ~= 0)
                len = lps(len);
            else 
                lps(i) = 0;
                i = i + 1;
            end
        end
    end
end

% Example usage:
txt = 'ABABDABACDABABCABAB';
pat = 'ABABCABAB';
KMPSearch(pat, txt);

注意：在 MATLAB 中，数组下标从 1 开始，因此在实现中需要注意下标的控制。