#include <iostream>
#include <cstring>

class String{
    // вывод из потока
    friend std::ostream& operator<<(std::ostream& os, const String& s) {
        for (size_t i = 0; i < s.length(); ++i){
            os << s[i];
        }
        return os;
    }
    // ввод в поток
    friend std::istream& operator>>(std::istream& in, String& s) {
        s.clear();
        char c;
        while (in.get(c)) {
            if (c == '\n') {
                break;
            }
            s.push_back(c);
        }
        return in;
    }
private:
    char* str = new char[1]; // указатель на массив
    size_t sz = 0; // размер
    size_t maxsz = 1; // максимально возможный размер str

    void growBuffer() {
        maxsz *= 2;
        char* newstr = new char[maxsz];
        memcpy(newstr, str, sz);

        delete[] str;
        str = newstr;
    }

    void cutBuffer() {
        maxsz /= 2;
        char* newstr = new char[maxsz];
        memcpy(newstr, str, sz);

        delete[] str;
        str = newstr;

    }

public:
    // Конструктор по умолчанию
    String() {}

    // Конструктор от C-style строки
    String(const char* s): str(new char[strlen(s)]), sz(strlen(s)), maxsz(strlen(s)) {
        memcpy(str, s, sz);
    }
    // Конструктор от двух параметров (size, char)
    String(const size_t n, const char c): str(new char[n]), sz(n), maxsz(n) {
        memset(str, c, n);
    }

    // Конструктор копирования
    String(const String &s): str(new char[s.sz]), sz(s.sz), maxsz(s.sz)  {
       memcpy(str, s.str, s.sz);
    }

    // Оператор присваивания
    String& operator=(const String& other) {
        String copy = other;
        sz = copy.sz;

        maxsz = other.maxsz;
        delete[] str;

        str = new char[maxsz];
        memcpy(str, copy.str, sz);

        return *this;
    }

    // Квадратные скобки для конст. строк
    const char& operator[](const size_t pos) const {
        return str[pos];
    }
    // Квадратные скобки для неконст. строк
    char& operator[](const size_t pos) {
        return str[pos];
    }

    // length() - размер строки
    size_t length() const {
        return sz;
    }

    // push_back(char), pop_back() за O(1) амортизиованно
    void push_back(const char c) {
        if (sz == maxsz) {
            growBuffer();
        }
        str[sz] = c;
        sz++;
    }

    void pop_back() {
        if (sz <= (maxsz / 4)) {
            cutBuffer();
        }
        --sz;
    }
    // front(), back() - ссылка на начальный и на последний символы строки

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

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

    char& back() {
        return str[sz - 1];
    }

    const char& back() const {
        return str[sz - 1];
    }

    // += - добавить к строке символ или строку. Символ за O(1) учётно.
    String& operator+=(const String& s) {
        for (size_t i = 0; i < s.sz; ++i) {
            push_back(s[i]);
        }
        return *this;
    }

    String& operator+=(const char c) {
        push_back(c);
        return *this;
    }
    // + -  оператор складывания 1) строки с символом 2) символ и строка 3) строка и строка

    // find(substring), rfind(substring) - индекс вхождения строки с начала и с конца (length - в противном случае)

    size_t find(const String& subStr) const {
        int flag = 1;
        for (size_t i = 0; i < sz; ++i) {
            for (size_t j = 0; j < subStr.sz; ++j) {
                if (i + j >= sz) {
                    flag = 0;
                    break;
                }
                if (str[i + j] != subStr[j]) {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1) {
                return i;
            }
            flag = 1;
        }
        return sz;
    }

    size_t rfind(const String& subStr) const {
        int flag = 1;
        for (size_t i = 0; i < sz; ++i) {
            for (size_t j = 0; j < subStr.sz; ++j) {
                if ((sz - 1 - i + j) >= sz) {
                    flag = 0;
                    break;
                }
                if (str[sz - 1 - i + j] != subStr[j]) {
                    flag = 0;
                    break;
                }
            }

            if (flag == 1) {
                return sz - 1 - i;
            }
            flag = 1;
        }
        return sz;
    }
    // substr(start, count) - вернуть подстроку длины count начиная со start
    String substr(size_t start, size_t count) const {
        String res(count, '\0');
        for (size_t i = start; i < start + count; ++i) {
            res[i - start] = str[i];
        }
        return res;
    }

    // empty() - проверка на пустоту
    bool empty() const {
        if (sz == 0) {
            return true;
        } else {
            return false;
        }
    }

    // clear() - очистка строки
    void clear() {
        delete[] str;
        sz = 0;
        maxsz = 1;
        str = new char[1];
    }
    // ~ Деструктор
    ~String() {
        delete[] str;
    }
};

bool operator==(const String& lhs, const String& rhs) {
    if (lhs.length() != rhs.length()) {
        return false;
    }
    for (size_t i = 0; i < lhs.length(); ++i) {
        if (lhs[i] != rhs[i]){
            return false;
        }
    }
    return true;
}

String operator+(const char lstr, const String& rstr) {
    String copy(1, lstr);
    copy += rstr;
    return copy;
}

String operator+(const String& lstr, const char rstr) {
    String copy = lstr;
    copy.push_back(rstr);
    return copy;
}

String operator+(const String& lstr, const String& rstr) {
    String copy = lstr;
    copy += rstr;
    return copy;
}