неправильный алгоритм сопоставления строк - PullRequest
Новая
       6

неправильный алгоритм сопоставления строк

0 голосов
/ 25 августа 2018

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

function naive(string, str) {
    for (let i = 0; i <= string.length - str.length; i++) {
        if (string[i] == str[0]) {
            let counter = 1

            for (let j = 1; j <= str.length; j++) {
                if (string[i + j] == str[j]) {
                    counter++;
                    console.log(counter)
                } else
                    counter = 0;
            }

            if (counter == str.length) {
                console.log(`${counter} pattern matched at ${i}`)
            }
        } else
            console.log('nothing matched')
    }
}

Ответы [ 2 ]

0 голосов
/ 25 августа 2018

Вам не нужно делать всю эту итерацию и сравнение самостоятельно.Вот более простая версия вашей функции: 

function naive(string, str) {
  var counter = 0, 
    i = string.indexOf(str, 0);  //find first occurance of str in string

  while(i !== -1){
    ++counter;  //we have a match, count one up
    console.log(`counter %i, index %i`, counter, i);
    i = string.indexOf(str, i+1);  //find next occurance 
  }
  return counter;
}

console.log("result", naive("lorem upsum", "m"));
0 голосов
/ 25 августа 2018 

var match_found = false;
function naive(string, str){
  for(let i =0; i <= string.length - str.length; i++){
      if(string[i] == str[0]){
        let counter= 1
            for(let j = 1; j < str.length; j++){
                if(string[i + j] == str[j]){    
                  counter++;
                }else{
                  break;
                }
            }
        if(counter == str.length){ 
          console.log('Pattern matched at ' + i);
          match_found = true;// can break; here if you wish to, else it will give you all matches present
        }
      }
  }
  if(match_found === false){
    console.log(str + ' not found in ' + string);
  }
}

naive('abcdgggabcdggg','ggg');

  • Вы increment counter, когда есть совпадение, но вам нужно break цикл, где есть mismatch.

  • Ваше внутреннее условие цикла должно иметь j < str.length вместо j <= str.length, потому что индекс начинается с 0.

  • else console.log('nothing matched'). Вы не можете just instantly решить это. Если строковый индекс не совпадает, вам все еще нужно искать остальные индексы. Лучший способ добиться этого - сохранить для него логический флаг, как показано в приведенном выше коде.

...