// NAME         : Cormac Roth
// SCHOOL       : Kalamazoo AMSC
// DIVISION     : Senior-5
// PROGRAM      : ACSL Difference Factor
// CONTEST      : Round 2
// DATE         : January 2020
// DESCRIPTION  : Calculates the difference factor of two strings

#include 
#include 
#include 
#include 
using namespace std;

//declare variables
int fact;

//function to convert to all uppercase, no symbols
string convert(string old)
{
    string temp = "";
    
    for(int a = 0; a < old.length(); ++a)
    {
        if(old[a] >= 'A' && old[a] <= 'Z')
        {
            temp += old[a];
        }
        else if(old[a] >= 'a' && old[a] <= 'z')
        {
            temp += old[a] - 32;
        }
    }
    
    return temp;
}

//function to find difference factor
void split(string first, string second)
{
    //declare variables
    int p1 = 0, p2 = 0;
    string hold = "";
    
    //loop for descending sizes
    for(int a = (int) min(first.length(), second.length()); a > 0; --a)
    {
        //find the first alphabetical match for the size
        for(int pos1 = 0; pos1 <= first.length() - a; ++pos1)
        {
            for(int pos2 = 0; pos2 <= second.length() - a; ++pos2)
            {
                if(first.substr(pos1, a) == second.substr(pos2, a))
                {
                    if(hold == "" || hold > first.substr(pos1, a))
                    {
                        hold = first.substr(pos1, a);
                        p1 = pos1;
                        p2 = pos2;
                    }
                }
            }
        }
        
        //if a match is found, split and add to the difference factor
        if(hold != "")
        {
            string f = "", s = "";
            for(int b = 0; b < p1; ++b)
                f += first[b];
            
            for(int b = 0; b < p2; ++b)
                s += second[b];
            
            split(f, s);

            f = "";
            s = "";
            for(int b = p1 + a; b < first.length(); ++b)
                f += first[b];
            
            for(int b = p2 + a; b < second.length(); ++b)
                s += second[b];
            
            split(f, s);

            fact += a;
            return;
        }
    }
}

int main()
{
    //declare variables
    string first, second;
    
    ifstream fin ("2sr_testdata.txt");
    
    //loop for all runs
    for(int run = 1; run <= 5; ++run)
    {
        //read in strings
        getline(fin, first);
        getline(fin, second);
        fact = 0;
        
        //convert to upper alpha only
        first = convert(first);
        second = convert(second);
        
        //calculate and print difference factor
        split(first, second);
        
        cout << fact << endl;
    }
    
    return 0;
}