查找字符串多重集的所有組合中的線性時間

給定字符的袋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

查找字符串多重集的所有組合中的線性時間

回答

相關問題