/////////////////////////////////////////////
// MT2Q5 - String Compare

#include <string>
#include <tuple>
#include <algorithm>
#include <iostream>

struct ICompString
{
  using Interval = std::pair<size_t, size_t>;
  using Positions = std::pair<Interval, Interval>;

  virtual ~ICompString() {}
  static ICompString* Create();
  virtual bool compare(const std::string& s1, const std::string& s2, size_t matchLength) = 0;
  virtual Positions locate() = 0;
};

class CompString : public ICompString
{
public:
  bool compare(const std::string& s1, const std::string& s2, size_t matchLength);
  Positions locate();
private:
  Interval Interv1{ 0, 0 };
  Interval Interv2{ 0, 0 };
};

ICompString* ICompString::Create()
{
  return new CompString;
}

bool CompString::compare(const std::string& s1, const std::string& s2, size_t matchLength)
{
  bool match = false;
  for (size_t i = 0; i < s1.size() - matchLength + 1; ++i)
  {
    for (size_t j = 0; j < s2.size() - matchLength + 1; ++j)
    {
      if (s1[i] == s2[j])
      {
        for (size_t k = 0; k < std::min(s1.size(), s2.size()); ++k)
        {
          if (s1[i + k] != s2[j + k])
          {
            if (k >= matchLength)
            {
              Interv1.first = i;
              Interv1.second = i + k - 1;
              Interv2.first = j;
              Interv2.second = j + k - 1;
              return true;
            }
            else
              break;
          }
        }
      }
    }
  }
  return false;
}

CompString::Positions CompString::locate()
{
  Positions pos;
  pos.first = Interv1;
  pos.second = Interv2;
  return pos;
}

int main()
{
  std::cout << "\n  MT2Q5 - Strings Compare";
  std::cout << "\n =========================\n";

  std::string first = "this is a string";
  std::string second = "here is an ardvarrk";

  ICompString* pComp = ICompString::Create();
  size_t matchLength = 5;
  bool match = pComp->compare(first, second, matchLength);
  if (match)
  {
    CompString::Positions pos = pComp->locate();
    size_t start = pos.first.first;
    size_t end = pos.first.second - start + 1;
    std::cout << "\n  strings \"" << first << "\" and \""
      << second << "\" contain the substring \""
      << first.substr(start, end) << "\"\n\n";
  }
  else
    std::cout << "\n  no matching substring of length " << matchLength << " or more was found\n\n";
}