Здравствуйте, Ehri, Вы писали:
E> Есть два байтовых массива, один длины N, другой длины K <= N. В массивах записаны числа(из рассчёта один байт — один разряд), разделённые строго одиночными пробелами. В рамках каждой из строк числа не повторяются. Числа могут быть очень большими, например 100-значными.
E> Написать алгоритм, который находит числа, представленные в обеих строках, и выводит на экран их позиции в этих строках.
E> Алгоритм должен работать время не более O(N) и использовать динамически выделяемой памяти не более О(K).
Построить по K что-то вроде
суффиксного дерева, но не на всех возможных суффиксах, а на числах из K. В листьях дерева будем хранить индекс начала соответствующего числа.
Далее бежим по N и для каждого числа ищем в дереве.
Дерево строится за O(К). Требует памяти O(K). Пробег по N и поиск — O(N).