Дано:

1. Не ориентированный граф G

2. pattern поиска - графа такой что:

   a) pattern - не ветвящийся путь

   aa) pattern - может и не быть подграфом G

Найти (Сделать) реализацию алгоритма:

можно поддерживать граф G:

1. добавлять новые pattern

2. искать совпадения по pattern (совпадения считаются верными если нашелся путь из вершины G частично или полностью равный pattern)

пример (частичного совпадения):

G: a1 -> a2 -> a3 -> a4
    \
      a5 -> a6

pattern: a1 -> a5 (буедт частичным совпадением)
pattern: a1 -> a6 (не буедт частичным совпадением)

и возвращать найденные варианты "пройденные" до листьев

пример:

G: a1 -> a2 -> a3 -> a4
                \
                  -> a5 -> a6

pattern: a1 -> a2
find result:
1. a1 -> a2 -> a3 -> a4
2. a1 -> a2 -> a3 -> a5 -> a6

• main algorithm
• additional functions
• aproximal time eval at O(n) notation

1. Find equal history tail

2. Traverse to leaf (save leaf's)

3. Traverse to root from each saved leaf aggregating traversed path

1. build tree from string

2. merge trees by equal leading part

example:

G1: a1 -> a2 -> a3
G2: a1 -> a2 -> a6

G3 will be merge result of G1 and G2 smth like this

G3: a1 -> a2 -> a3
            \ -> a6

1. Find equal history tail

   • find required sub-tree head if G is not connected graph O(n) < log2(n)
     (bin search in ordered array of n head)
   • at founded head - traverse s node until find history tail O(n) < logX (n)
     at current subtree with n node, where X = max child degree

2. Traverse to leafs (save leaf's)

   • if at sub graph G1 contain t leaf then O(n) < t * logX (n)
     at current subtree with n node, where X = max child degree

3. Traverse to root from each saved leaf aggregating traversed path

   • if at sub graph G1 contain t leaf then O(n) < t * logX (n)
     at current subtree with n node, where X = max child degree