оценивая мой код big-O, наивное сопоставление с образцом

Я пытаюсь решить упражнение 32.1-2 из книги CLRS, посвященное строковым алгоритмам, наивному поиску по шаблону.

Предположим, что все символы в шаблоне P различны. Покажите, как ускорить NAIVE-STRING-MATCHER, чтобы он выполнялся за время O(n) для текста из n символов.

Итак, я пытаюсь оптимизировать наивное решение грубой силы, которое я придумал, но я не думаю, что смогу сделать что-то лучше, чтобы сократить общее время работы до O (n).

 <?php

 //naive search
$a = array('a', 'b', 'u', 'c');
$b = array('a','b','u','c','a','b','u','c','b','a','b','u','c','b', 'a', 'b','c');
//index     0   1  2    3  4   5    6   7  8    9  10   11 12  13  14    15   16
$n = count($b);
$k = count($a);
$counter = 0;

    for($i=0;$i<$n - $k ;$i++){   // big- O (n)


 //since its "exact string matching problem" i am testing here so i don't dive into second loop unless the ith character of B is matching the first char of the pattern 

     if($b[$i] == $a[0]){
            for($j=$i; $j<$k; $j++){ // big O(k)
                if($b[$j] == $a[$j])
                    $bool = true;
                else {
                    $bool = false;
                    break;   
                }
            }
            if($bool){
                echo "Found at index: ".$i."<br>";
                $counter++;
            }
// since pattern match cant overlap with another one, so when one is found jump by K iteration, here is all what I could do about the pattern's value being distinct, is there any possible optimization I can do
           $i = $i + $k - 1;   
        }


    }

echo $counter;
?>

Я, конечно, сократил время выполнения для этого конкретного экземпляра, но представьте себе в худшем случае текст со всеми его символами, установленными на «a», я буду погружаться во второй цикл каждый раз, когда это O (k * n).

Что такое большое O алгоритма? и могу ли я получить более эффективное решение?


php algorithm pattern-matching clrs
person Mohamed Kira    schedule 11.08.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вы также правильно поняли идею («поскольку совпадение с образцом не может пересекаться с другим»). Что-то вроде этого должно работать для основного цикла:

for($i=0;$i<$n - $k ;$i++){
            for($j=0; $j<$k; $j++){
                $last_matched = $j + $i;
                if($b[$j + $i] == $a[$j])
                    $bool = true;
                else {
                    $bool = false;
                    break;   
                }
            }
            if($bool){
                echo "Found at index: ".$i."<br>";
                $counter++;
            }
           // this line is important
           $i = $last_matched + 1;   
        }

Обратите внимание на важную строку. Здесь мы указываем алгоритму начать следующую попытку сопоставления после того, как наше предыдущее сопоставление не удалось (или закончилось). Это связано с тем, что в шаблоне есть разные символы, и нет возможности, чтобы, если вы уже сопоставили j символов, а затем не смогли сопоставить символ j + 1, реальное совпадение будет перекрывать эту область (если они перекрываются, некоторые символы в шаблоне должны быть одинаковыми). , что является противоречием).

Теперь сложность измененного алгоритма будет O(n). Это связано с тем, что условие if во внутреннем цикле будет выполняться только один раз для каждого символа текста (помните, что после завершения или разрыва внутреннего цикла мы начинаем внешний цикл после его последней позиции).

P.S.: Умножение на сложность циклов часто бывает правильным, но вы не всегда получаете максимально узкую границу.

person usamec    schedule 11.08.2017
comment
Что касается последней заметки, которую вы написали, насколько я знаю, мы используем Θ для обозначения точной верхней границы и O для обозначения верхней границы. будет ли мое решение оптимальным, если в упражнении требуется Θ, а не O? - person Mohamed Kira; 11.08.2017
comment
я думаю, что недостаточно хорошо понял вопрос, потому что лучший алгоритм сопоставления с образцом KMP работает на O (m + n) - person Mohamed Kira; 11.08.2017
comment
Люди, которые используют O и Thera взаимозаменяемо (хотя они разные). Мои утверждения также верны для тета-обозначения. - person usamec; 11.08.2017
comment
Также алгоритм KMP является общим алгоритмом сопоставления с образцом, который будет работать в этом случае. Но этот частный случай является хорошим упражнением алгоритмического мышления, и его расширение может привести к алгоритму Бойера-Мура. - person usamec; 11.08.2017