#include <cstring>
#include <sstream>

class String {
 private:
  size_t capacity_ = 0;
  size_t size_ = 0;
  char* t_ = nullptr;

  void realloc() {
    if (4 * size_ <= capacity_) {
      reserve(size_ * 2);
    }
  }

  void realloc(size_t capacity) {
    if (capacity > capacity_) {
      reserve(capacity * 2);
    }
  }

 public:
  ~String() { delete[] t_; }

  String() = default;

  String(char x) {
    size_ = 0;
    capacity_ = 1;
    t_ = new char[capacity_];
    t_[size_++] = x;
  }

  String(const char* t) {
    size_ = strlen(t);
    capacity_ = size_;
    t_ = new char[capacity_];
    memcpy(t_, t, size_ * sizeof(char));
  }

  String(size_t n, char c) : capacity_(n), size_(n), t_(new char[capacity_]) {
    memset(t_, c, size_ * sizeof(char));
  }

  String(const String& s)
      : capacity_(s.size_), size_(s.size_), t_(new char[capacity_]) {
    memcpy(t_, s.t_, size_ * sizeof(char));
  }

  void swap(String& s) {
    std::swap(capacity_, s.capacity_);
    std::swap(size_, s.size_);
    std::swap(t_, s.t_);
  }

  String& operator=(const String& s) {
    String copy(s);
    swap(copy);
    return *this;
  }

  bool operator==(const String& s) const {
    if (size_ != s.size_) return false;

    for (size_t i = 0; i < size_; ++i) {
      if (t_[i] != s.t_[i]) return false;
    }

    return true;
  }

  char& operator[](size_t x) { return t_[x]; }

  char operator[](size_t x) const { return t_[x]; }

  size_t length() const { return size_; }

  char& front() { return t_[0]; }

  const char& front() const { return t_[0]; }

  char& back() { return t_[size_ - 1]; }

  const char& back() const { return t_[size_ - 1]; }

  void reserve(size_t capacity) {
    char* p = new char[capacity];
    capacity_ = capacity;

    if (t_) {
      size_ = std::min(size_, capacity);
      memcpy(p, t_, size_ * sizeof(char));
      delete[] t_;
    }
    t_ = p;
  }

  void push_back(char x) {
    realloc(size_ + 1);
    t_[size_++] = x;
  }

  void pop_back() {
    size_--;
    realloc();
  }

  String& operator+=(const String& s) {
    realloc(size_ + s.size_);
    memcpy(t_ + size_, s.t_, s.size_ * sizeof(char));
    size_ += s.size_;
    return *this;
  }

  size_t find(const String& s) const {
    for (size_t i = 0; i < size_ - s.size_ + 1; ++i) {
      bool is_equal = true;
      for (size_t j = 0; j < s.size_; ++j) {
        if (t_[i + j] != s.t_[j]) is_equal = false;
      }
      if (is_equal) {
        return i;
      }
    }
    return size_;
  }

  size_t rfind(const String& s) const {
    for (size_t i = size_ - 1; i >= s.size_; --i) {
      bool is_equal = true;
      for (int j = s.size_; j--;) {
        if (t_[i - s.size_ + j + 1] != s.t_[j]) is_equal = false;
      }
      if (is_equal) {
        return i - s.size_ + 1;
      }
    }
    return size_;
  }

  String substr(size_t i, size_t count) const {
    String s;
    s.reserve(count);
    memcpy(s.t_, t_ + i, count * sizeof(char));
    s.size_ = count;
    return s;
  }

  bool empty() { return size_ == 0; }

  void clear() {
    size_ = 0;
    delete[] t_;
    t_ = nullptr;
    capacity_ = 0;
  }
};

String operator+(const String& s, const String& g) {
  String res = s;
  res += g;
  return res;
}

std::istream& operator>>(std::istream& in, String& s) {
  s.clear();
  char x;
  in >> x;

  while (!in.eof()) {
    if (std::isspace(x)) break;
    s.push_back(x);
    x = in.get();
  }

  return in;
}

std::ostream& operator<<(std::ostream& out, const String& s) {
  for (size_t i = 0; i < s.length(); ++i) {
    out << s[i];
  }
  return out;
}