#include <cstdint>
#include <string>
#include <iostream>

// I den här uppgiften antar vi att alla tecken i strängar är bokstäver
// (specifikt gemener), d.v.s. 'a' till 'z' endast.

std::uint64_t const SmallPrime { 31 };
std::uint64_t const LargePrime { 1000000009 };

// hasha n tecken i s, med start på index i
std::uint64_t hash(std::string const& s, unsigned i, unsigned n)
{
    std::uint64_t result { 0 };
    std::uint64_t multiplier { 1 };
    for (unsigned j { 0 }; j < n; ++j)
    {
        int c { s[i + j] };
        result     = (result + c * multiplier) % LargePrime;
        multiplier = (multiplier * SmallPrime) % LargePrime;        
    }
    return result;
}

// hasha hela strängen s
std::uint64_t hash(std::string const& s)
{
    return hash(s, 0, s.size());
}

// Beräkna base^exponent
std::uint64_t pow(std::uint64_t base, std::uint64_t exponent)
{
    if      (exponent == 0) return 1;
    else if (exponent == 1) return base;

    if (exponent % 2 == 1)
        return base * pow(base, exponent - 1);

    std::uint64_t result { pow(base, exponent / 2) };
    return result * result;
}

bool contains(std::string const& text, std::string const& pattern)
{
    // tomma strängen är en substräng till alla strängar
    if (pattern.empty()) return true;

    std::size_t n { text.size() };
    std::size_t m { pattern.size() };

    // TODO: Implementera ett glidande hashvärde som jämför hashvärdet för
    // pattern med hashvärdet för alla delsträngar i text.
    //
    // Notera: Om en delsträngar har samma hashvärde som pattern är inte det
    // säkert att detta är en match, så i den situationen måste du fortfarande
    // kontrollera huruvida det faktiskt är en matchning.

    return false;
}

int main()
{
    std::string text, pattern;
    while (true)
    {
        std::cout << "Enter word: ";
        std::cin >> text;

        if (text == "quit")
            break;

        std::cout << "Enter pattern: ";
        std::cin >> pattern;

        if (contains(text, pattern))
            std::cout << text << " contains " << pattern << std::endl;
        else
            std::cout << "No result" << std::endl;
    }
}