查找字符串多重集的所有组合中的线性时间

给定字符的袋B（多集）与尺寸m和大小为n的串文本•

你避难所。在线性时间O（n）中，是否有可能在S中找到可由B（4！= 24个组合）创建的所有子串？查找字符串多重集的所有组合中的线性时间

实施例：

S = abdcdbcdadcdcbbcadc (n=19) 
B = {b, c, c, d} (m=4) 
Result: {cdbc (Position 3), cdcb (Position 10)}

我发现的最快的解决方案是保留一个计数器对于各个字符并将其与袋在每个步骤中进行比较，从而运行时是O（n×m个）。如果需要，可以显示算法。

来源

2011-11-05 owning Mahowny

感谢您的回答。该add()和remove()方法必须改变，以正确地使算法的工作。

add(c): 
    if hist[c] > 0 and histrun[c] < hist[c] then 
     histrunsum++ 
    else 
     histrunsum-- 

    histrun[c] = histrun[c] + 1 


remove(c): 
    if histrun[c] > hist[c] then 
     histrunsum++ 
    else 
     histrunsum-- 

    histrun[c] = histrun[c] - 1

说明： histrunsum可以被看作是一个分数的两个多集如何都相同。（c）：当在多重集合中出现的字符比在多重集合中出现的次数少时，该字符的额外出现必须被“奖励”，因为histrun多重集合越来越接近历史组合multiset 。如果在hetrun集合中至少有相同或更多的字符，并且其他字符是负数。其中除去炭的被加权正时，它的在histrun多重集> HIST多重集数目象add（c）中，：

删除（c）中。

示例代码（PHP）：

function multisetSubstrings($sequence, $mset) 
{ 
    $multiSet = array(); 
    $substringLength = 0; 
    foreach ($mset as $char) 
    { 
     $multiSet[$char]++; 
     $substringLength++; 
    } 

    $sum = 0; 
    $currentSet = array(); 
    $result = array(); 

    for ($i=0;$i<strlen($sequence);$i++) 
    { 

     if ($i>=$substringLength) 
     { 
      $c = $sequence[$i-$substringLength]; 

      if ($currentSet[$c] > $multiSet[$c]) 
       $sum++; 
      else 
       $sum--; 

      $currentSet[$c]--; 
     } 


     $c = $sequence[$i]; 

     if ($currentSet[$c] < $multiSet[$c]) 
      $sum++; 
     else 
      $sum--; 

     $currentSet[$c]++; 

     echo $sum."<br>"; 


     if ($sum==$substringLength) 
      $result[] = $i+1-$substringLength; 
    } 


    return $result; 
}

来源

2011-11-07 14:40:57

我不能按照你的逻辑，说实话;你能解释你的改变的目的吗？（即在你的版本中histrunsum是什么意思，以及为什么需要改变） – zeuxcg

有一个办法做到在O（N），假设我们只在长度为m的子串兴趣（否则它是不可能的，因为有字符串中的所有字符的包，你必须返回s的所有子串，这意味着O（n^2）的结果不能在O（n）中计算）。

的算法如下：

转换袋子直方图：

hist = [] 
for c in B do: 
    hist[c] = hist[c] + 1

初始化我们要修改（histrunsum是的总数正在运行的直方图字符）：
```
histrun = [] 
histrunsum = 0 
```

我们需要两个操作s：在直方图中添加一个字符并将其删除。它们操作如下：

add(c): 
    if hist[c] > 0 and histrun[c] < hist[c] then: 
     histrun[c] = histrun[c] + 1 
     histrunsum = histrunsum + 1 

remove(c): 
    if histrun[c] > 0 then: 
     histrun[c] = histrun[c] - 1 
     histrunsum = histrunsum + 1

实质上，histrun捕获是在当前子存在于B个字符的量。如果histrun等于hist，则我们的子串具有与B相同的字符。如果histrunsum等于B的长度，则histrun等于hist。
现在，将前m个字符添加到histrun;如果histrunsum等于B的长度;发出第一个子串;现在，直到我们到达字符串的末尾，删除当前子字符串的第一个字符并添加下一个字符。
添加，删除是O（1）因为HIST和histrun是数组;检查，如果HIST等于histrun由histrunsum比较长度（B）完成的，因此它也O（1）。循环迭代计数为O（n），结果运行时间为O（n）。

来源

2011-11-05 20:33:21 zeuxcg

使用散列。对于多重集中的每个字符，分配一个唯一的素数。通过乘以与数字相关联的质数来计算任意字符串的散列，数量与该数字的频率相同。

例如：CATTA。令C = 2，A = 3，T = 5。哈希= 2 * 3 * 5 * 5 * 3 = 450

散列multiset（将其视为字符串）。现在检查输入字符串，并计算长度为k的每个子字符串的哈希（其中k是多重字符中的字符数）。检查此散列是否与多重集合散列匹配。如果是的话，那么这是一个这样的事件。

该散列可以在线性时间很容易地计算如下：

让多重集= {A，A，B，C}，A = 2，B = 3，C = 5。

多重集的散列= 2 * 2 * 3 * 5 = 60

让文本= CABBAACCA

（ⅰ）CABB = 5 * 2 * 3 * 3 = 90

（ⅱ）现在，下一个字母是A，丢弃的字母是第一个字母C，所以新散列=（90/5）* 2 = 36

（iii）现在，A被丢弃，A也被添加，所以新散列=（36/2）* 2 = 36

（iv ）现在B被丢弃，并且C被添加，所以hash =（36/3）* 5 = 60 =多重集合散列。因此，我们发现了一个这样的需求发生 - BAAC

此过程显然需要O（n）时间。

来源

2012-08-16 07:15:45 arya

查找字符串多重集的所有组合中的线性时间

回答

相关问题