// Test if a string is a rotation of another.

#define CATCH_CONFIG_MAIN
#include <catch.hpp>

#include <fmt/format.h>
#include <experimental/string_view>
#include <string>
#include <unordered_set>

using string_view = std::experimental::string_view;

bool is_rotation(string_view lhs, string_view rhs) {
  // Confirm using one call to isSubstring.
  // Facts:
  //   Must be the same length.
  //   Must have the same letters and counts.
  //   Adjacents must be the same.

  // Brute force version.
  for (auto it = lhs.cbegin(); it != lhs.cend(); it++) {
    std::string rotated{it, size_t(lhs.cend() - it)};
    rotated += std::string{lhs.cbegin(), size_t(it - lhs.cbegin())};

    if (rotated == rhs) {
      return true;
    }
  }
  return false;
}

bool is_rotation_2(const std::string& lhs, const std::string& rhs) {
  // Clever version: if lhs is a rotation of rhs, then lhs is a
  // substring of rhs+rhs.
  if (lhs.length() != rhs.length()) {
    return false;
  }

  return (lhs + lhs).find(rhs) != std::string::npos;
}

TEST_CASE("cc19", "rotate") {
  CHECK(is_rotation("waterbottle", "waterbottle") == true);
  CHECK(is_rotation("waterbottle", "erbottlewat") == true);
  CHECK(is_rotation("waterbottle", "erbotltewat") == false);
  CHECK(is_rotation("waterbottle1", "erbottlewat1") == false);

  CHECK(is_rotation_2("waterbottle", "waterbottle") == true);
  CHECK(is_rotation_2("waterbottle", "erbottlewat") == true);
  CHECK(is_rotation_2("waterbottle", "erbotltewat") == false);
  CHECK(is_rotation_2("waterbottle1", "erbottlewat1") == false);
}