Небольшая оптимизация инкрементального поиска

Инкрементальный поиск это когда вы пишете и сразу же происходит поиск после ввода каждой новой буквы. Как правило он всегда ещё и с автодополнением. Вы можете увидеть инкрементальность поиск по этой странице (Ctrl+F) и набирая по одной букве слово «информационные».

	Длина слова	Макс. совпадения букв (с начала слова)
1	информатор	10	7
2	информация	10	9
3	информационный	14	13
4	инфляция	8	3
5	инагурация	10	2
6	ингалятор	9	2
7	дезинформация	13	0
8	информационные	14	14

А в чём проблема?

Допустим что во время набора вы случайно сделали ошибку и затёрли предыдущею букву чтобы исправить её на правильную.
В этот момент произойдёт новый поиск. Или допустим вы ищите «информационные технологии», уже написали «информационные», оно вам нашлось но вы на автомате продолжаете набирать « технологии». Хоть такого совпадения точно нет, на каждое новое ваше нажатие тоже будет происходить новый поиск.
Если поиск занимает не много времени, то пользователь этого не заметит.
Но теперь представьте что операция поиска у вас дорогая. Например вы ищете по очень большому тексту, или допустим у вас автодополнение и для каждого поиска дёргается запрос на сервер.
Для таких случаев следует сделать проверку имеет ли смысл вообще продолжать поиск.

Для этого нужно сохранять результат максимального совпадения от предыдущих поисков:

1. Набираем «информ», максимальное совпадение 6 первых символов в словах «информатор», «информация», «информационный», «информационные».
2. Теперь делаем ошибку «информиц». Поиск не удался, смотрим предыдущее максимальное совпадение — 6, а мы уже набрали 8 букв, т.е. если дальше набирать фразу то можно даже не пытаться что-то найти.
3. Замечаем, жмём ← Backspace, получаем «информи» — 7 букв, а у нас максимальное предыдущее 6, опять не делаем поиск.
4. Исправили до «информ» и продолжили поиск снова каждый раз проверяя предыдущий результат.

Техническая реализация

Обратите внимание что мы предполагаем что пользователем будет меняться только концовка критерия поиска. А пользователь взял, скопировал откуда то слово и вставил его в строку поиска. Поменялся сразу весь критерий поиска а не просто его концовка.
Чтобы разрулить такую ситуацию сохраняйте не просто число, а и весь найденный фрагмент целиком и сверять с ним.

Для такого поиска нужно будет написать специальную функцию которая рассчитает максимальное совпадение:

function maxIntersect(string, subString) {
 for (i = 0; i < string.length && i < subString.length; i++) {
  if (string[i] != subString[i]) {
   return i + 1;
  }
 }
 return i + 1;
}

Когда-то я делал поиск в Firefox'е по тексту закона и таких тормоза я очень заметил. Chrome таким вроде не грешит. З.Ы. Файл Excel иллюстрирующий работу механизма.