Да, это возможно; Google Scholar перечисляет несколько статей по теме. Хитрость заключается в первоначальном назначении частичных суффиксов начальным процессорам; это должно быть выбрано так, чтобы каждый процессор мог независимо найти свой участок дерева. Как только это будет сделано, обычные операции с суффиксным деревом могут быть выполнены довольно эффективно. Я не знаю ни одного публичного примера реализации.