Алгоритм поиска подстроки
function subStr(_substring, _string) { var substring = _substring.split(''), string = _string.split(''), found = false, k = 1; for(var i = 0; i < string.length; i++) { if(string[i] == substring[0]) { for(var j = 1, l = i + 1; j < substring.length; j++, l++) if (string[l]) { if(string[l] == substring[j]) { k++; } else { k = 1; break; } } if(k == substring.length) { found = true; break; } else { i = l; } } } return found; } Можно ли сделать эффективнее? Интересует чисто с академической, так сказать, стороны :) |
а чем вам indexOf не угодил?
var string = 'qwe'; var substring = 'we'; alert(string.indexOf(substring) !== -1 ? 'found' : 'not found'); |
devote,
ну про стандартные конструкции языка я в курсе, интересует именно со стороны эффективности алгоритма. Ну представим на минуту, что в javascript`e отсутствуют стандартные способы поиска подстроки и необходимо его реализовать. Я вот тут ещё что подумал - к символу строки ведь можно обратиться по индексу, правильно ли я понимаю, что движок в этом случае при каждом подобном обращении преобразует строку к массиву? Целесообразно ли я в начале функции сам преобразовываю строки в массивы :-? |
Цитата:
function strpos(substring, string) { return string.split(substring).length === 2; } alert(strpos('привет', 'привет мир!'));вариант 2: function strpos(substring, string) { var index = 0, subindex = 0; while(subindex < substring.length && index < string.length) { if (substring[subindex] === string[index]) { subindex++; } else { index -= subindex; subindex = 0; } index++; } return subindex > 0; } alert(strpos('привет', 'привет мир!')); |
Чет ты перемудрил.
function stringContains(string, substring) { if (substring.length === 0) return false; for (var i = 0; i < string.length; i++) { if (string[i] === substring[0]) { for (var j = 1; j < substring.length; j++) { if (string[i + j] !== substring[j]) return false; } return true; } } return false; } Может я тоже) |
Цитата:
P.S. конечно название я не совсем правильное функций сделал, но это сами придумывайте. |
danik.js,
хотя не, у тебя тоже вполне компактно |
Дзен-трансгуманист,
ну тогда релиз: function strpos(substring, string) { var index = 0, subindex = 0; var subStrLen = substring.length; var strLen = string.length; while(subindex < subStrLen && index < strLen) { if (substring.charCodeAt(subindex) === string.charCodeAt(index)) { subindex++; } else { index -= subindex; subindex = 0; } index++; } return subindex > 0; } alert(strpos('привет', 'привет мир!'));частое обращение к свойству .length тоже влияет на производительность. |
Хром 28, разница чуть меньше: x8
|
zilker,
:write: function subStr(_substring, _string) { var found = _string.split(_substring)[0].length return found < _string.length } alert(subStr('ty', 'qwerty')) |
Часовой пояс GMT +3, время: 22:49. |