#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

std::size_t overlap(const std::string& key, const std::string& word);
std::size_t forwardOverlap(const std::string&, const std::string&);
std::size_t reverseOverlap(const std::string&, const std::string&);

struct wordInfo
{
    std::size_t expectedOverlap;
    std::string word;
};

void testOverlap(const std::string& key, const std::vector<wordInfo>& words)
{
    for (auto& word : words)
    {
        std::size_t overlapSize = overlap(key, word.word);
        if (overlapSize != word.expectedOverlap)
        {
            std::cout << "overlap failed on key \"" << key;
            std::cout << "\" with word \"" << word.word << "\"\n";
            return;
        }
        //else
        //{
        //    std::cout << "overlap succeeded on key \"" << key;
        //    std::cout << "\" with word \"" << word.word << "\": ";
        //    std::cout << overlapSize << " overlap.\n";
        //}
    }

    std::cout << "overlap test successful!\n";
}


int main()
{
    std::vector<wordInfo> words =
    {
        { 0, "fact" }, 
        { 0, "war" }, 
        { 0, "stare" }, 
        { 2, "cent" }, 
        { 4, "facet" }, 
        { 4, "endface" },
        { 2, "alfalfa" }
    };

    testOverlap("face", words);
}

std::size_t overlap(const std::string& key, const std::string& word)
{
    return std::max(forwardOverlap(key, word), reverseOverlap(key, word));
}

std::size_t forwardOverlap(const std::string& k, const std::string& w)
{
    std::size_t overlapSize = std::min(k.size(), w.size());

    while (overlapSize > 0)
    {
        std::string keyFragment = k.substr(k.size() - overlapSize);
        std::string wordFragment = w.substr(0, overlapSize);

        if (keyFragment == wordFragment)
            break;

        --overlapSize;
    }

    return overlapSize;
}

std::size_t reverseOverlap(const std::string& k, const std::string& w)
{
    std::size_t overlapSize = std::min(k.size(), w.size()) ;

    while (overlapSize > 0)
    {
        std::string keyFragment = k.substr(0, overlapSize);
        std::string wordFragment = w.substr(w.size() - overlapSize);

        if (keyFragment == wordFragment)
            break;

        --overlapSize;
    }

    return overlapSize;
}