Подумал над несколькими вариантами, но везде лажа выходит. и по времени и по памяти. непонятно что за природа таблицы и запросов, возможно зная её можно придумать что-то по-лучше для вашего случая. Могу предложить метод с такой же сложностью что и ваш, который делает некоторые отсечения при удачном раскладе, но требует препроцессинга таблицы и использования хеш-таблиц либо замены строк на числа. посортим столбцы как-нибудь имперически-эвристически оптимально. все строки в ячейках заменим на числа. строим бор для строк таблицы. имея строку-запрос начинаем поиск в ширину по нашему бору. состояние описывается вершиной бора, и количеством совпавших ячеек. заведем глобальную переменную отвечающую за максимум совпадений на данном шаге. на завершающей стадии поиска в ширину возникают отсечение, если мы уже никак не доберём нужное число совпадений, улучшающее максимум. можно юзать 40 очередей для "дейкстры", чтобы идти по бору глубже пока есть совпадения.

Можно использовать что-то вроде бора. Предположим что каждому атрибуту выдано число (номер буквы в алфавите). Каждая строка -- некоторое слово из 40 букв. После построения бора пускаем по нему 0-1_бфс. Если надо перейти по букве, где нет совпадения, то вес ребра единица, иначе 0. В худшем случае работает так же плохо, но если строка-запрос отличается от ответа на небольшое число символов, то должно работать хорошо.

Для "совсем общего" случая алгоритма хорошего вероятно не будет, а частности у вас не описаны: насколько схожи между собой строки таблицы, как много среди них звёздочек, как много у вас запросов, сколько вам надо времени на запрос и т.п.

Кроме того непонятна относительная ценность совпадения буква-буква и буква-звёздочка (а также звёздочка-буква). Скажем запрос "A B C" идеально совпадает со строкой "* * *", а со строкой "A B V" он совпадает неидеально, зато две буквы верные.

Могу предложить алгоритм для "довольно общего" случая, например пусть у нас M строк по N ячеек:

1. для каждого столбца подготовим массив индексов строк, отсортированный по возрастанию ячеек в этом столбце.

2. Для обработки запроса, подготовим массив R результата, т.е. массив оценок для каждой из строк, длиной M чисел, изначально там нули.

3. Когда имеем запрос, то для каждого K-го (K=1..N) массива за O(log(M)) находим пару индексов A и B, между которыми лежат все номера строк, в которых K-я ячейка совпадает с K-й ячейкой из запроса.

4. Пробегаем по полученному диапазону индексов и для каждого индекса I увеличиваем R[I] на единицу.

5. Совпадение со звёздочками обрабатываем отдельно, аналогично, только увеличивать можно не на единицу, а на стоимость совпадения со звёздочкой.

6. В конце отыскиваем максимум в массиве R. Эта позиция соответствует "оптимальной" строке.

Быстродействие, очевидно, зависит от того как много похожих ячеек в строках. Если все строки одинаковы и запрос совпадает с ними со всеми, мы получим нечто слегка похуже O(M*N). Если много различающихся строк, то массив R будет забиваться за время стремящееся к O(log(M)*N) — если совпадений по 1 на столбец — и потом поиск лучшего варианта за O(N) — его тоже можно уменьшить вплоть до O(M) если R представить хэшмэпой.

В общем, всё от характера данных зависит. Возможно вам и не нужна оптимизация %)

можно использовать БД.