Введение

Данные

Работа с деревом проиходит с помощью двух структур. Одна структура описывает узлы дерева, другая рёбра. 
// узел
node_st{
	link_st *links;	// список рёбер узла
	node_st *suff;	// суффиксная связь
};

// ребро
link_st{
	link_st *next;		// следующее ребро узла в списке
	char *first; 		// ссылка на текст ребра
	char *last; 		// ссылка на конец текста ( 0 - если конец не  фиксирован)
	node_st *node;		// узел растущий на конце ребра
        str_st *std_id;		// ссылка на данные текста ребра
	unsigned long user;	// пользовательские данные
};

// текст ребра
str_st{
	char *first;		// начало строки
	char *end;		// конец строки
	int win_size;		// размер окна (пока не поддерживается)
	unsigned long user;	// пользовательские данные
};

Внутри библиотеки стуктуры имеют дополнительные поля. Но для простоты и совместимости, их внешнее представление остаётся неизменным.

Работа

  1. MemoryInit(); - установка внутренних переменных (требуется один раз при старте программы)
  2. id=AddString(text); - начало работы с новой строкой
  3. UpdateString(id,size); - достроить дерево (строка увеличивается на заданный размер)
  4. ClearTree(); - удалить дерево и очистить память

Пример: 
   char *text="133575351";
   MemoryInit();
   str_st *id=AddString(text);
   node_st *root=UpdateString(id,strlen(text));

Текст можно добавлять в дерево по частям. Размер нашего текста равен 9 байтам. Строку UpdateString(id,9) можно заменить на два вызова UpdateString(id,6); UpdateString(id,3); - что приведёт к тому же результату. К сожалению пока что можно увеличивать только последнюю строку, из тех что вы начали добавлять в дерево. Если увеличивать разные строки в перемешку, то дерево будет построено неправильно (я вообще не знаю возможно ли сделать смешанное увеличение, т.е. пока не думал об этом).

Тонкости

Для построения дерева из множества строк, необходимо указывать уникальные концы отдельных строк, без этого правильное дерево построить невозможно. Поскольку библиотека работает любыми данными, то концы обозначать нечем. Для корректной работы программа расставляет в дереве фиктивные узлы, Из которых растёт только одна ветка. Расстановка фиктивных узлов производится автоматически, в тот момент когда вы начинаете работу с новой строкой. Часть фиктивных узлов после работы можно удалить, но пока что этим не занимался. В распределитель памяти на будушее встроенна возможность освобождать выделенные элементы.

За просессом(прогрессом) построения большого дерева можно налюдать извне. Из дополнительного потока, наблюдая на переменной EndText у текушей строки. Растёт эта величина линейно, по мере обработки новых символов.

Немного о ...

Для того чтобы найти в строке максимальную повторяющую подстроку, достаточно пройтись по дереву, и найти узел с максимальной глубиной из которого выходит не меньше двух строк, принадлежащих данной строке.

В случае если приходится искать общую подстроку двух строк, то необходимо найти узел из которого выходит по одной ветке принадлежащей каждой из строк. Но поскольку мы не обозначаем концы строк отдельными символами, то дополнительно придётся проверить концы самих строк на совпадение. Возможна ситуация когда с концов в строках будет больше совпадающих символов, чем в найдёных через дерево отрезках. Проблема отпадёт целиком, если каждая строка будет кончаться каким-либо уникальным символом, например символами с кодом 1,2,3.... Может быть со временем я сделаю механизм который специально устраняет эту неприятность.

Ссылки

icq:133575351
email:lawnmower-man@mail.ru

http://flatassembler.net/