如何将最多k个不匹配的模式匹配算法复杂度优化至O(nk.log(n))

我正在尝试优化最多k个不匹配的模式匹配问题的运行时间，采用滑动窗口结合二分查找与滚动哈希结构统计不匹配数。

任务定义 #

给定整数参数k，以及两个字符串t = t₀t₁···tₘ₋₁和p = p₀p₁···pₙ₋₁，若p与t的子串t[i:i+p) = tᵢtᵢ₊₁···tᵢ₊ₙ₋₁的差异位置不超过k个，则称p在t的位置i处最多有k个不匹配地出现。

输入输出与约束 #

• 输入格式：每行输入包含整数k及两个小写拉丁字母组成的字符串t、p。
• 约束：0 ≤ k ≤ 5，1 ≤ |t| ≤ 200000，1 ≤ |p| ≤ min{|t|, 100000}，所有t总长度≤200000，所有p总长度≤100000。
• 输出格式：找出所有满足条件的位置，输出数量及位置列表。

现有代码与问题 #

import java.util.*;
import java.util.stream.Collectors;
import java.io.*;
import java.math.BigInteger;

public class matching_with_mismatches {
    private static int prime = 2000000033;
    private static int multiplier = 19;

    private long[] prefixHashT;
    private long[] prefixHashP;

    public List<Integer> solve(int k, String text, String pattern) {
        ArrayList<Integer> pos = new ArrayList<>();

        int tLen = text.length();
        int pLen = pattern.length();

        prefixHashT = new long[tLen + 1];
        prefixHashP = new long[pLen + 1];

        // Compute the hashes for prefixes
        prefixHashT[0] = 0;
        for (int i = 1; i <= text.length(); i++) {
            prefixHashT[i] = (prefixHashT[i - 1] * multiplier + text.charAt(i - 1)) % prime;
        }

        prefixHashP[0] = 0;
        for (int i = 1; i <= pattern.length(); i++) {
            prefixHashP[i] = (prefixHashP[i - 1] * multiplier + pattern.charAt(i - 1)) % prime;
        }

        // For each pair of p and substring of t
        for (int i = 0; i <= tLen - pLen; i++) {

            int start = i; // index of "text"
            int end = i + pLen - 1; // index of "text"
            int misMatches = 0;
            
            // Perform at most k binary searches for mismatches
            while (start <= end) {
                int mid = (start + end) / 2;

                long pSubHash = hashSubstring(prefixHashP, start - i, mid - i);
                long tSubHash = hashSubstring(prefixHashT, start, mid);

                if (pSubHash == tSubHash) { // Match
                    start = mid + 1;
                } else if (start == end) { // Pinpoint the mismatch aka mid
                    start = mid + 1;
                    end = i + pLen - 1;
                    if (++misMatches > k) break;
                } else { // Hashes don't match, but there may be mismatch before this mid
                    end = mid;
                }
            }
            
            if (misMatches > k) continue;
            else pos.add(i);
        }

        return pos;
    }

    public long hashSubstring(long[] prefixHash, int start, int end) throws RuntimeException {
        if (start < 0 || end + 1 > prefixHash.length) throw new RuntimeException("start and end must be within prefix length");

        start++;
        end++;

        int len = end - start + 1;
        if (len < 0) throw new RuntimeException("length must be positive");

        long y = new BigInteger(Integer.toString(multiplier))
            .modPow(new BigInteger(Integer.toString(len)), new BigInteger(Integer.toString(prime)))
            .longValue(); // (multiplier ^ len) % prime

        return ((prefixHash[end] - prefixHash[start - 1] * y) % prime + prime) % prime;
    }

    public void run() {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        in.lines().forEach(line -> {
            StringTokenizer tok = new StringTokenizer(line);
            int k = Integer.valueOf(tok.nextToken());
            String s = tok.nextToken();
            String t = tok.nextToken();
            List<Integer> ans = solve(k, s, t);
            out.format("%d ", ans.size());
            out.println(ans.stream()
                    .map(n -> String.valueOf(n))
                    .collect(Collectors.joining(" "))
            );
        });
        out.close();
    }

    static public void main(String[] args) {
        new matching_with_mismatches().run();
    }
}

当前实现的时间复杂度为O(mk.log(n))（m为文本串长度，n为模式串长度），但题目要求将复杂度优化至O(nk.log(n))，请问如何实现这一优化？

内容的提问来源于Stack Exchange，提问作者Andy Nguyen