Можно ли использовать алгоритм Кнута-Морриса-Пратта для сопоставления строк в тексте?

У меня есть код KMP в PHP, который может сделать сопоставление строк между словами в текст. Интересно, могу ли я использовать алгоритм KMP для сопоставления строк между текстом. Это возможно или нет? и как я могу использовать его для поиска соответствия строки между двумя текстами.

Вот ядро ​​алгоритма KMP:

<?php
class KMP{
function KMPSearch($p,$t){
$result = array();
$pattern = str_split($p);
$text    = str_split($t);
$prefix = $this->preKMP($pattern);
// print_r($prefix);

// KMP String Matching
$i = $j = 0;
$num=0;
while($j<count($text)){
while($i>-1 && $pattern[$i]!=$text[$j]){
// if it doesn't match, then uses then look at the prefix table
$i = $prefix[$i];
}
$i++;
$j++;
if($i>=count($pattern)){
// if its match, find the matches string potition
// Then use prefix table to swipe to the right.
$result[$num++]=$j-count($pattern);
$i = $prefix[$i];
}
}
return $result;
}

// Making Prefix table with preKMP function
function preKMP($pattern){
$i = 0;
$j = $prefix[0] = -1;
while($i<count($pattern)){
while($j>-1 && $pattern[$i]!=$pattern[$j]){
$j = $prefix[$j];
}
$i++;
$j++;
if(isset($pattern[$i])==isset($pattern[$j])){
$prefix[$i]=$prefix[$j];
}else{
$prefix[$i]=$j;
}
}
return $prefix;
}
}
?>

Я вызываю этот класс в свой index.php, если я хочу использовать, чтобы найти слово в тексте.

Это шаг, который я хочу, чтобы мой код сделал:
(1). Я ввожу текст 1
(2). Я ввожу текст 2
(3). Я хочу, чтобы текст 1 стал шаблоном (каждое отдельное слово в тексте 1 рассматривается как шаблон)
(4). Я хочу, чтобы мой код мог найти каждый шаблон текста 1 в тексте 2
(5). Наконец, мой код может показать мне, какой процент сходства.

Надеюсь, что вы все можете помочь мне или научить меня. Я везде искал ответ, но пока не могу его найти. По крайней мере, вы можете научить меня.

0

Решение

Если вам просто нужно найти все слова, присутствующие в обоих текстах, у вас нет алгоритма поиска строк, чтобы сделать это. Вы можете просто добавить все слова из первого текста в хеш-таблицу, перебрать второй текст и добавить слова, находящиеся в хеш-таблице, в список вывода.

Вы можете использовать trie вместо хеш-таблицы, если вам нужна линейная временная сложность в худшем случае, но я бы начал с хеш-таблицы, потому что она проста в использовании и, вероятно, будет достаточно для практических целей.

-1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector