Изменения

Перейти к: навигация, поиск

Алгоритм Укконена

86 байт добавлено, 08:24, 15 апреля 2015
м
Реализация
== Реализация ==
public static class '''struct Node {''' '''int ''' begin; '''int ''' end; '''int ''' depth; // distance in characters from root to this nodeрасстояние от корня до до текущей вершины в символах '''Node ''' parent; '''Node[] ''' children; '''Node ''' suffixLink;
public static '''Node ''' buildSuffixTree(CharSequence s) {: '''int ''' n = s.length(); '''byte[] ''' a = new byte[n]; '''for (int ''' i = 0; i < ..n; i++) a[i] = (byte) ALPHABET.indexOf(s.charAt(i)); '''Node ''' root = new '''Node'''(0, 0, 0, null); '''Node ''' node = root; '''for ''' (int i = 0, tail = 0; i < n; i++, tail++) { '''Node ''' last = null; '''while (''' tail <tex>\geqslant</tex>= 0) { '''Node ''' ch = node.children[a[i - tail]]; '''while ''' (ch != null && tail <tex>\geqslant</tex>= ch.end - ch.begin) { tail -= ch.end - ch.begin; node = ch; ch = ch.children[a[i - tail]]; } '''if (''' ch == null) { node.children[a[i]] = new Node(i, n, node.depth + node.end - node.begin, node); '''if ''' (last != null) last.suffixLink = node; last = null; } else { byte t = a[ch.begin + tail]; '''if (''' t == a[i]) { '''if (''' last != null) last.suffixLink = node; '''break;''' } else { Node splitNode = new Node(ch.begin, ch.begin + tail, node.depth + node.end - node.begin, node); splitNode.children[a[i]] = new Node(i, n, ch.depth + tail, splitNode); splitNode.children[t] = ch; ch.begin += tail; ch.depth += tail; ch.parent = splitNode; node.children[a[i - tail]] = splitNode; '''if (''' last != null) last.suffixLink = splitNode; last = splitNode; } } '''if (''' node == root) { --tail; } else { node = node.suffixLink; } } } '''return ''' root; }
== См. также==
275
правок

Навигация