//NAME          :   Aidan Eichman
//SCHOOL        :   Kalamazoo AMSC
//DIVISION      :   Senior-5
//PROGRAM       :   ACSL Difference Factor
//CONTEST       :   Round 2
//DATE          :   January 28, 2020
//DESCRIPTION   :   Given two strings, calculate the ACSL
//              :   Difference Factor (ADF), ignoring all non-alphabetic
//              :   characters and convert all letters to uppercase.
//              :   Find the longest common substring contained in the two
//              :   strings until there are no more common substrings, then output
//              :   the sum of the lengths of all the longest common substrings.

#include 
#include 
#include 
#include 
#include 

using namespace std;

//method to find the longest common substring in the two strings
string LCS(const string & str1, const string & str2)
{
    vector> LCS(str1.length() + 1, vector(str2.length() + 1, 0));
    
    int longest = 0;
    string long_str = "";
    for (size_t i = 1; i <= str1.length(); ++i)
    {
        for (size_t j = 1; j <= str2.length(); ++j)
        {
            if (isalpha(str1[i -1]) && str1[i - 1] == str2[j - 1])
            {
                LCS[i][j] = LCS[i - 1][j - 1] + 1;
                if (LCS[i][j] > longest)
                {
                    longest = LCS[i][j];
                    long_str = str1.substr(i - longest, longest);
                }
                else if (LCS[i][j] == longest)
                {
                    string temp_str = str1.substr(i - longest, longest);
                    if (temp_str.compare(long_str) < 0)
                    {
                        long_str = temp_str;
                    }
                }
            }
        }
    }
    return long_str;
}

//method to find the ACSL Difference Factor by adding the lengths of the
//substrings that are common in the two strings
int ADF(const string & str1, const string & str2)
{
    string common = LCS(str1, str2);
    if (common == "") return 0;
    
    int idx1 = str1.find(common);
    int idx2 = str2.find(common);
    
    int total = 0;
    
    string left1 = str1.substr(0, idx1);
    string left2 = str2.substr(0, idx2);
    
    total += ADF(left1, left2);
    
    string right1 = str1.substr(idx1 + common.size());
    string right2 = str2.substr(idx2 + common.size());
    
    total += ADF(right1, right2);
    
    return common.size() + total;
}

//method to remove the spaces from the input
void remove_spaces(string & str)
{
    int num_chars = 0;
    for (int i = 0; i < str.length(); ++i)
    {
        if (str[i] != ' ')
        {
            str[num_chars++] = str[i];
        }
    }
    
    str.erase(num_chars, string::npos);
}

int main()
{
    //input file
    ifstream fin ("2sr_testdata.txt");
    
    //signature
    cout<<"Aidan Eichman\nAPCS\nACSL Difference Factor ACSL Senior-5\nJanuary 2020\n\n";
    
    for(int q = 0; q < 5; ++q)
    {
        //declare and read in variables
        string str1, str2;
        getline(fin, str1);
        getline(fin, str2);
        
        //converts the strings into uppercase
        transform(str1.begin(), str1.end(), str1.begin(), ::toupper);
        transform(str2.begin(), str2.end(), str2.begin(), ::toupper);
        
        //removes the spaces from the strings
        remove_spaces(str1);
        remove_spaces(str2);
        
        //declare and initializes the result
        int result = ADF(str1, str2);
        
        //outputs the result
        cout << result << '\n';
    }
    
    return 0;
}