Приблизительный поиск по списку строк

Итак, да, я читал о том, как можно использовать расстояние редактирования между строками, чтобы решить, насколько «близки» две строки к каждой. Другой. Этот алгоритм, реализованный в виде динамической задачи, занимает время O (mn), где m и n - длины текста и шаблона соответственно. Поэтому, если мне нужно сопоставить строку с 5000 с лишним другими строками, это займет МНОГО времени, что для моего приложения просто неприемлемо. Есть ли более быстрое решение, которое можно реализовать? Я не против променять место для хранения на время.

Я видел приложение под названием «Swype» на Android, которое делает нечто подобное. Он ищет ваш запрос в собственной базе данных и предлагает результаты. Как это работает так быстро?

Примечание : пожалуйста, не предлагайте фреймворки, такие как Lucene, потому что я не могу работать в этом случае на J2ME.