Теоретический материал
Ниже приведен код разобранной части решения задачи.
type
TEl=record
First : int; // Номер строки, описанной выше
i, j : int; // Границы подстроки, написанной на ребре
link : array ['a'..'z'] of int; // Ссылки на «детей»
end;
var
bor : array [0..max] of TEl;
uk : int;
//Добавление строки j
procedure Add(j: int);
var cur, t, x : int;
begin
cur := 0; t := 1;
while t <= length(a[j]) do begin
if bor[cur].link[a[j][t]] = 0 then begin
//Добавление новой вершины
inc(uk);
fillchar(bor[uk], sizeof(bor[uk]), 0);
bor[cur].link[a[j][t]] := uk;
bor[cur].first := j;
bor[uk].first := j;
bor[uk].i := t;
bor[uk].j := length(a[j]);
Break;
End
else begin
//Переход по существующему ребру
bor[cur].first := j;
cur := bor[cur].link[a[j][t]];
x:=bor[cur].i;
//Подсчет количества совпадающих символов на ребре
while (x <= bor[cur].j) and (x <= length(a[j])) and
(a[j][x] = a[bor[cur].first][x]) do inc(x);
dec(x);
if x <> bor[cur].j then begin
//Ребро нужно делить
//Старая вершина отходит продолжению старой ветви
//Создание вершины деления
inc(uk);
fillchar(bor[uk], sizeof(bor[uk]), 0);
bor[uk].first := bor[cur].first;
bor[uk].i := x + 1;
bor[uk].j := bor[cur].j;
bor[uk].link := bor[cur].link;
bor[cur].first := j;
bor[cur].j := x;
fillchar(bor[cur].link, sizeof(bor[cur].link), 0);
bor[cur].link[a[bor[uk].first][x+1]] := uk;
if x <> length(a[j]) then begin
//Создание вершины для новой строки
inc(uk);
fillchar(bor[uk], sizeof(bor[uk]), 0);
bor[uk].first := j;
bor[uk].i := x + 1;
bor[uk].j := length(a[j]);
bor[cur].link[a[bor[uk].first][x+1]] := uk;
end;
Break;
end
else begin //Ребро не нужно делить
t := x + 1;
bor[cur].first := j;
end;
end;
end;
end;
//Поиск всех путей по Alt из from в поддереве cur
procedure Dfs(from, cur : int);
var lp : char;
begin
if cur <> 0 then begin
//Попытка добавить путь из from в текущую вершину
if g[from,bor[cur].first] > bor[cur].i + 1 then
g[from,bor[cur].first] := bor[cur].i + 1;
end;
for lp := 'a' to 'z' do
if bor[cur].link[lp] <> 0 then dfs(from, bor[cur].link[lp]);
end;
Begin
uk := 0; fillchar(bor[0], sizeof(bor[0]), 0); bor[0].j := -1;
// Инициализация бора
for j := N downto 1 do Add(j); // Добавляем слова
for i := N downto 1 do begin
Add(i); Dfs(i,0); // Обновляем данные и ищем все искомые пути из вершины
end;
End.