Найти все комбинации мультимножества в строке за линейное время

Question

Вы дали сумку B (мультимножество) символов с размером m и строковым текстом S размера n. Можно ли найти все подстроки, которые могут быть созданы B (4! = 24 комбинации) в S за линейное время O (n)?

Пример:

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

Самое быстрое решение, которое я нашел, - это сохранить счетчик для каждого символа и сравнивать его с Bag на каждом шаге, таким образом, время выполнения равно O (n * m). Алгоритм может быть показан при необходимости.

Answer 1

Есть способ сделать это в O (n), предполагая, что нас интересуют только подстроки длины m (в противном случае это невозможно, потому что для пакета, в котором есть все символы в строке, вам придется вернутьвсе подстроки s, что означает результат O (n ^ 2), который не может быть вычислен в O (n)).

Алгоритм следующий:

• Преобразовать пакет в гистограмму:

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

• Инициализировать текущую гистограмму, которую мы собираемся изменить (Histrunsum - это общее количество символов в гиструне):

  histrun = []
  histrunsum = 0
  

• Нам нужно две операции: добавить символ в гистограмму и удалить его.Они работают следующим образом:

  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 равно his, у нашей подстроки те же символы, что и у B. Histrun равно his, если значение Histrunsum равно длине B.

• Теперь добавьте первые m символов к Histrun;если Histrunsum равен длине B;вывести первую подстроку;теперь, пока мы не достигнем конца строки, удалите первый символ текущей подстроки и добавьте следующий символ.

• add, remove - O (1), так как Hist и Histrun являются массивами;проверка, соответствует ли значение Hist к значению Histrun, производится путем сравнения значения Histrunsum с длиной (B), поэтому оно также равно O (1).Счетчик итераций цикла равен O (n), итоговое время выполнения равно O (n).

Answer 2

Спасибо за ответ. Для правильной работы алгоритма необходимо изменить методы 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 можно рассматривать как оценку того, насколько идентичны оба мультимножества.

add (c): когда в множественном множестве Histrun меньше числа появлений символа, чем в множественном множестве исторических данных, то дополнительное появление этого символа должно быть "вознаграждено", так как множественный набор исторических значений приближается к множественному множеству исторических данных. Если в наборе Histrun уже есть хотя бы одинаковые или несколько символов, а дополнительный символ отрицателен.

remove (c): аналогично add (c), где удаление символа взвешивается положительно, когда его число находится в multisetistrun> Hist MultiSet.

Пример кода (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;
}

Answer 3

Используйте хеширование. Для каждого символа в мультимножестве присвойте УНИКАЛЬНОЕ простое число. Вычислите хеш для любой строки, умножив простое число, связанное с числом, на столько раз, сколько частота этого числа.

Пример: CATTA. Пусть C = 2, A = 3, T = 5. Хеш = 2 * 3 * 5 * 5 * 3 = 450

Хэш мультимножества (трактуйте его как строку). Теперь просмотрите входную строку и вычислите хэш каждой подстроки длины k (где k - количество символов в мультимножестве). Проверьте, совпадает ли этот хеш с хешом мультимножества. Если да, то это один из таких случаев.

Хеши могут быть очень легко вычислены за линейное время следующим образом:

Пусть мультимножество = {A, A, B, C}, A = 2, B = 3, C = 5.

Хэш мультисети = 2 * 2 * 3 * 5 = 60

Пусть текст = CABBAACCA

(i) CABB = 5 * 2 * 3 * 3 = 90

(ii) Теперь следующая буква - А, а отброшенная буква - первая, С. Итак, новый хэш = (90/5) * 2 = 36

(iii) Теперь A отбрасывается и A также добавляется, поэтому новый хэш = (36/2) * 2 = 36

(iv) Теперь B отбрасывается, а C добавляется, поэтому hash = (36/3) * 5 = 60 = multi-set hash. Таким образом, мы нашли один такой требуемый случай - BAAC

Эта процедура, очевидно, займет O (n) время.