Как лучше распараллелить поиск подстроки в строке?

Question

[Shach]

Задача: Распараллелить поиск подстроки в строке.

Если использовать тривиальный алгоритм (прикладывать образец во все места строки), то распараллелить можно, распределив интервалы по потокам (например, 1 поток - прикладывать к 1..4 позиции, 2 поток - 5..8 позиции и т.д.). Какие еще алгоритмы поиска подстроки также можно распараллелить?(использовать тривиальный способ не хочется)

Средства разработки: С, POSIX Threads.

Answer 1

[Curly Brace]

да имхо любой. чем меньше объем текста для поиска, тем лучше (ведь врядли вы это хотите распаралеливать для 16 символьной строки)

Answer 2

[sivabur]

Смотрите посчитайте оптимальное количество потоков на винде= количествам ядер.
Проанализируйте скорость посика вс троках разной длины. Может ыбть что будет быстрей чем с распаралеливанием.
И на основе етого в зависимости от длина распаралеливайте строки или не рапаралеливайте.Смотря что будет быстрей ведь для выделения потока тоже требуется время.