string - 在线性时间内匹配字符串的模式

Question

给定两个字符串 S 和 T，其中 T 是模式字符串。查找字符串 S 中是否存在任何模式字符串的加扰形式作为 SubString，如果存在则返回起始索引。

示例:

字符串 S: abcdef字符串 T:efd

字符串 S 有“def”，搜索字符串 T 的组合:“efd”。

我找到了一个运行时间为 O(m*n) 的解决方案。我正在研究一个线性时间解决方案，我曾经使用 HashMaps(静态的，为字符串 T 维护，另一个是前一个 HashMap 的动态副本，用于检查 T 的当前子字符串)。我会开始检查失败的下一个字符。但在最坏的情况下，这在 O(m*n) 中运行。我想获得一些指示以使其在 O(m+n) 时间内工作。任何帮助将不胜感激。

Answer 1

首先，我想知道字符串 S 的边界长度 (m)和图案T长度 (n) .

存在一个通用的想法，但基于它的解决方案的复杂性取决于模式长度。复杂性从 O(m) 变化至 O(m*n^2)对于 length<=100 的短模式和 O(n)对于长模式。

Fundamental theorem of arithmetic指出每个整数都可以唯一地表示为素数的乘积。

想法 - 我猜，你的字母表是英文字母。所以，字母表的大小是 26。让我们用第一个素数替换第一个字母，用第二个素数替换第二个字母，依此类推。我的意思是以下替换:
a->2
b->3
c->5
d->7
e->11 等等。

让我们将与某个字符串的字母对应的素数的乘积表示为 prime product(string) .例如，primeProduct(z)将是 101作为101是第 26 个素数，primeProduct(abc)将是 2*3*5=30 , primeProduct(cba)也将是5*3*2=30 .

为什么我们选择素数？如果我们更换 a ->2; b ->3，c->4，我们无法破译示例 4 - 是“c”还是“aa”。

短模式案例的解决方案:对于字符串 S，我们应该计算所有前缀的线性时间素积。我的意思是我们必须创建数组 A 使得 A[0] = primeProduct(S[0]) , A[1] = primeProduct(S[0]S[1]) , A[N] = primeProduct(S) .示例实现:

A[0] = getPrime(S[0]);
for(int i=1;i<S.length;i++)
    A[i]=A[i-1]*getPrime(S[i]);

搜索模式 T。计算 primeProduct(T)。对于所有 'windows'在与 pattern 具有相同长度的 S 中，将它的 primeProduct 与 primeProduct(pattern) 进行比较。如果 currentWindow 等于模式或 currentWindow 是模式的困惑形式(anagramm)，primeProducts 将相同。

重要提示!我们已经为 快速计算 primeProduct 准备了数组 A，用于S 的任何子串。 primeProduct of(S[i],S[i+1],...S[j]) = getPrime(S[i])*...*getPrime(S[j]) = A[j]/A[i-1] ;

复杂度:如果模式长度<=9，即使是'zzzzzzzzz'是101^9<=MAX_LONG_INT ;所有计算都符合标准 long 类型，复杂度为 O(N)+O(M)，其中 N 用于计算模式的 primeProduct，M 遍历 S 中的所有窗口 .如果 length<=100 你必须增加 mul/div long numbers 的复杂性，这就是复杂性变为 O(m*n^2) 的原因. 101^length 的长度是 O(N) 如此长的数字的 mul/div 是 O(N^2)

对于长度>=1000 的长模式，最好存储一些 HashMap (质数，度数)。前缀数组将成为散列映射数组和 A[j]/A[i-1] trick 会变​​成 differenceBetween(A[j] and A[i-1] hashmaps key sets).