Можно попробовать воспользоваться алгоритмом Рабина-Карпа поиска подстроки в строке.
Пусть есть подстрока sub
длины m
и строка s
длины n
, в которой мы ищем подстроку.
- Для начала вычислим хэш от подстроки
sub
- В строке
s
для каждой подстроки, длины m
, вычислим её хэш. Если хэш этой подстроки и строки sub
совпадают, то, потенциально, мы нашли вхождение подстроки sub
в строку s
.
- Проверим, что вхождение действительно имеет место быть, вручную сравнив строку
sub
и подстроку строки s
, с которой совпал хэш.
Аппроксимированно такой поиск будет требовать O(n + m)
времени, в худшем случае до O(n*m)
.
Для того, чтобы быстро пересчитывать хеш в строке s
используется кольцевой хэш, который позволяет быстро вычислить значение hash(s[1:m+1])
, зная значение hash(s[0:m])
. Вычисляется он по следующему принципу:
hash(s[0:m]) = p**(m-1) * ord(s[0]) +
p**(m-2) * ord(s[1]) +
... +
p * ord(s[m-2]) +
ord(s[m-1])
И для того, чтобы получить из этого хэша значение для s[1:m+1]
, достаточно выполнить следующие действия:
hash(s[1:m+1]) = hash(s[0:m]) * p - p**m * ord(s[0]) + ord(s[m])
что выполняется за константное время.
Требуется только выбрать нужное значение p
, рекомендуется обычно взять относительно большое простое число, например, 1000000007. Также стоит заранее посчитать и запомнить степени числа p
до p**m
.
Так как в этой задаче много подстрок, то если среди них есть строки совпадающей длины, можно воспользоваться уже вычисленными ранее значениями хэшей, т.е. если строка sub1
и строка sub2
имеют одинаковые длины, то для строки sub2
можно будет воспользоваться вычисленными хэшами строки s
для sub1
.
Для меньшего числа коллизий можно выбрать несколько значений p
и считать хэши для каждого из них, таким образом, необходимость проверять коллизию будет возникать реже, только если для всех p
значение хэша совпало.
grep -F
(илиfgrep
). Т.е. можно сначала получить все совпадения черезgrep
, а потом уже обрабатывать их как вам надо