%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NAME: KEVIN GUO                       %
% SCHOOL: MARKVILLE SECONDARY SCHOOL    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function lcs (n : string, m : string) : string % Returns the least common substring of n and m
    if n = "" or m = "" then
	result ""
    end if

    var l : int := 0 % Length of longest substring found
    var nEndIndex : flexible array 1 .. 0 of int % Locations of longest substrings found (can have equal length)
    var ls : array 1 .. length (n), 1 .. length (m) of int % Suffix tree

    for i : 1 .. length (n)
	for j : 1 .. length (m)
	    if n (i) = m (j) then
		ls (i, j) := 1
		if i > 1 and j > 1 then
		    ls (i, j) += ls (i - 1, j - 1)
		end if
		if ls (i, j) > l then
		    l := ls (i, j)
		    new nEndIndex, 1
		    nEndIndex (1) := i
		elsif ls (i, j) = l then
		    new nEndIndex, upper (nEndIndex) + 1
		    nEndIndex (upper (nEndIndex)) := i
		end if
	    else
		ls (i, j) := 0
	    end if
	end for
    end for

    if l = 0 then
	result ""
    end if

    var outStrs : array 1 .. upper (nEndIndex) of string
    for i : 1 .. upper (nEndIndex)
	outStrs (i) := ""
	for j : nEndIndex (i) - l + 1 .. nEndIndex (i)
	    outStrs (i) += n (j)
	end for
    end for

    var out : string := outStrs (1)
    for i : 2 .. upper (outStrs)
	if outStrs (i) < out then
	    out := outStrs (i)
	end if
    end for

    result out
end lcs

function format (s : string) : string % Removes non-alpha characters and converts string to uppercase
    var str : string := Str.Upper (s)
    var acc : string := ""
    for i : 1 .. length (s)
	if ord (str (i)) >= 65 and ord (str (i)) <= 90 then
	    acc += str (i)
	end if
    end for
    result acc
end format

function split (str1 : string, str2 : string) : int % Recursively splits and calculates adf, returns final adf
    var substr : string := lcs (str1, str2)
    %put str1, " ", str2, " ", substr
    if substr = "" then
	result 0
    end if

    var L1 : int := index (str1, substr) - 1
    var L2 : int := index (str2, substr) - 1
    var R1 : int := L1 + length (substr) + 1
    var R2 : int := L2 + length (substr) + 1

    result split (str1 (1 .. L1), str2 (1 .. L2)) + length (substr) + split (str1 (R1 .. length (str1)), str2 (R2 .. length (str2)))
end split

%%%%% MAIN CODE %%%%%
var input : int
open : input, "input_senior.txt", get % Input file 
var str1 : string
var str2 : string

for i : 1 .. 5
    get : input, str1 : *
    get : input, str2 : *
    str1 := format (str1)
    str2 := format (str2)
    put split (str1, str2)
end for