Мне кажется, что надо точнее сформулировать задачу - какие подстроки необходимо искать. Например, мне кажется точно никакого смысла искать строку с kino по подстроке ino нет и делать так никто не будет, а если кто-то будет, то это несущественная вариация.
Конечно, надо делать индекс FULLTEXT (ищет по 3 символам и больше), при этом каждое имя файла (строку) дополнить различными вариантами подстрок, которые можно получить из основной строки с учетом спец.символов - принятых маркеров разбиения строки. Например, строка примера примет вид:
Ochen_strashnoe_kino strashnoe_kino kino
Разбивать строки можно по _|.|,|\s|-|\|/|!|~| и т.д.
надо просмотреть как устроены строки и составить для них список маркеров-разделителей.