2

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

例子：

字符串 S：abcdef 字符串 T：efd

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

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

4

5 回答 5

3

首先，我想知道 string Slength(m)和 pattern Tlength的边界(n)。

存在一种一般性的想法，但基于它的解决方案的复杂性取决于模式长度。对于短模式和长模式，复杂性从O(m)到不等。O(m*n^2)length<=100O(n)

算术基本定理指出，每个整数都可以唯一地表示为素数的乘积。

想法 - 我猜，你的字母表是英文字母。所以，字母大小是 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'S 中与模式具有相同长度的所有内容，将其 primeProduct 与 primeProduct(pattern) 进行比较。如果 currentWindow 等于模式或者 currentWindow 是模式 primeProducts 的打乱形式（anagramm），则将是相同的。

重要的提示！我们为 S 的任何子串准备了数组 A 用于快速计算primeProduct 。= = ;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; 所有计算都适合标准长类型，复杂度为 O(N)+O(M)，其中 N 用于计算模式的 primeProduct，M 遍历 中的所有窗口。S如果长度<=100，则必须添加 mul/div 长数字的复杂性，这就是复杂性变为O(m*n^2). 101^length 的长度是 O(N) mul/div 这样长的数字是O(N^2)

对于长度>=1000 的长模式，最好存储一些哈希映射（素数，度数）。前缀数组将变成哈希映射数组，而A[j]/A[i-1]技巧将变成 differenceBetween(A[j] 和 A[i-1] 哈希映射的键集)。

于 2013-07-31T04:26:17.740 回答
1

这个 JavaScript 示例会是线性时间吗？

<script>

function matchT(t,s){
  var tMap = [], answer = []

  //map the character count in t
  for (var i=0; i<t.length; i++){
    var chr = t.charCodeAt(i)

    if (tMap[chr]) tMap[chr]++
    else tMap[chr] = 1
  }

  //traverse string
  for (var i=0; i<s.length; i++){
    if (tMap[s.charCodeAt(i)]){
      var start = i, j = i + 1, tmp = []

      tmp[s.charCodeAt(i)] = 1

      while (tMap[s.charCodeAt(j)]){
        var chr = s.charCodeAt(j++)

        if (tmp[chr]){
          if (tMap[chr] > tmp[chr]) tmp[chr]++
          else break
        }
        else tmp[chr] = 1
      }

      if (areEqual (tmp,tMap)){
        answer.push(start)
        i = j - 1
      }

    }
  }
  return answer
}

//function to compare arrays
function areEqual(arr1,arr2){
  if (arr1.length != arr2.length) return false
  for (var i in arr1)
    if (arr1[i] != arr2[i]) return false
  return true
}

</script>

输出：

console.log(matchT("edf","ghjfedabcddef"))
[3, 10]
于 2013-08-01T22:02:39.800 回答
0

让我们考虑给定的示例，字符串 S：abcdef 字符串 T：efd

创建一个由子字符串 T 中存在的字符组成的 HashSet。因此，该集合由 .

为子字符串 T: 1e1f1d生成一个标签。（每个字符的出现次数+字符本身，可以使用类似于计数排序的技术来完成）

现在我们必须为子字符串长度的输入生成标签。

让我们从第一个位置开始，它有字符 a。由于它不存在，我们不创建任何子字符串并移动到下一个字符 b。类似地，到字符 c 然后停在 d 处。

由于 d 存在于 HashSet 中，因此每次字符出现时开始生成标签（子字符串长度）。我们可以在不同的函数中执行此操作以避免清除计数数组（这样做将复杂度从 O(m*n) 降低到 O(m+n)）。如果在任何时候输入字符串不包含子字符串 T，我们可以从下一个位置开始生成标签（因为直到发生中断的位置不能是字谜的一部分）。

因此，通过生成标签，我们可以解决线性 O(m+n) 时间复杂度的问题。

m：输入字符串的长度，n：子字符串的长度。

于 2013-11-20T02:30:57.123 回答
0

如果字母表不是太大（比如 ASCII），那么就不需要使用散列来处理字符串。

只需使用一个与字母表大小相同的大数组，存在性检查就变成了O(1)。这样整个算法就变成了O(m+n)。

于 2013-07-31T00:44:47.663 回答
0

下面的代码用于 GFG 中的模式搜索问题，它在所有测试用例中都被接受，并且在线性时间内工作。

// { Driver Code Starts
import java.util.*;


class Implement_strstr
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        sc.nextLine();
        while(t>0)
        {
            String line = sc.nextLine();
            String a = line.split(" ")[0];
            String b = line.split(" ")[1];
            
            GfG g = new GfG();
            System.out.println(g.strstr(a,b));
            
            t--;
        }
    }
}// } Driver Code Ends




class GfG
{
    //Function to locate the occurrence of the string x in the string s.
    int strstr(String a, String d)
    {
      if(a.equals("") && d.equals("")) return 0;
      if(a.length()==1 && d.length()==1 && a.equals(d)) return 0;
        if(d.length()==1 && a.charAt(a.length()-1)==d.charAt(0)) return a.length()-1;
    int t=0;
    int pl=-1;
    boolean b=false;
    int fl=-1;    
    for(int i=0;i<a.length();i++)
    {
        if(pl!=-1)
        {
            if(i==pl+1 && a.charAt(i)==d.charAt(t))
            {
              t++;
              pl++;
              if(t==d.length())
              {
                  b=true;
                  break;
              }
            }
            else
            {
                fl=-1;
                pl=-1;
                t=0;
            }
        }
        else
        {
            if(a.charAt(i)==d.charAt(t))
            {
                fl=i;
                pl=i;
                t=1;
            }
        }

    }
        return b?fl:-1;
    }
}

这是问题的链接https://practice.geeksforgeeks.org/problems/implement-strstr/1

于 2021-05-14T14:18:33.137 回答