CONTEST#2 TASK#2

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#include <sstream>


struct Suffix
{
    int index;
    int rank[2];
};

int compare(struct Suffix a, struct Suffix b)
{
    return (a.rank[0] == b.rank[0]) ? (a.rank[1] < b.rank[1] ? 1 : 0) :
           (a.rank[0] < b.rank[0] ? 1 : 0);
}

std::vector<int> buildSuffixArray(std::string text)
{
    size_t n = text.size();
    std::vector<Suffix> suffixes(n, Suffix());

    for (int i = 0; i < n; ++i)
    {
        suffixes[i].index = i;
        suffixes[i].rank[0] = text[i] - 97;
        suffixes[i].rank[1] = ((i + 1) < n) ? (text[i + 1] - 97) : -1;
    }

    sort(suffixes.begin(), suffixes.end(), compare);

    std::vector<int> indices(n, 0);

    for (int i = 4; i < 2 * n; i = i * 2)
    {
        int rank = 0;
        int previousRank = suffixes[0].rank[0];
        suffixes[0].rank[0] = rank;
        indices[suffixes[0].index] = 0;

        for (int j = 1; j < n; ++j)
        {

            previousRank = suffixes[j].rank[0];
            suffixes[j].rank[0] = suffixes[j].rank[0] == previousRank &&
                                  suffixes[j].rank[1] == suffixes[j - 1].rank[1] ? rank : ++rank;

            indices[suffixes[j].index] = j;


        }

        for (int j = 0; j < n; ++j)
        {
            int nextIndex = suffixes[j].index + i / 2;
            suffixes[j].rank[1] = (nextIndex < n) ? suffixes[indices[nextIndex]].rank[0] : -1;
        }

        sort(suffixes.begin(), suffixes.end(), compare);
    }


    std::vector<int> suffixArray(n, 0);
    for (int i = 0; i < n; ++i)
        suffixArray[i] = suffixes[i].index;

    return suffixArray;
}

std::vector<int> search(const std::string &text, const std::string &pattern, const std::vector<int> &sufArr)
{
    std::vector<int> matched;
    bool flg = false;
    for (int i : sufArr)
    {
        if (pattern.size() > text.size() - i)
        {
            if (flg)
                break;
        } else if (pattern == text.substr(i, pattern.size()))
        {
            flg = true;
            matched.push_back(i);
        }

//   xaxaxaaaxaxaxaxaxaxaaaxaxaxaaxaxaxaaaxaxaxaaaxaxaxaa
    }

    std::sort(matched.begin(), matched.end());

    return matched;
}


std::vector<std::string> readInput(const std::string &path)
{
    std::ifstream file(path);
    std::vector<std::string> arr;
    std::string word;
    while (std::getline(file, word))
        arr.push_back(word);

    file.close();

    return arr;
}


std::string suffixArrayTask(const std::string &path)
{
//    std::cout << "Test: " << path;
    std::stringstream ss;
    std::vector<std::string> arr = readInput(path);
    std::vector<int> res;

    std::vector<int> suffixArray = buildSuffixArray(arr[0]);
    for (int i = 1; i < arr.size(); ++i)
    {

        std::string pattern = arr[i];
        res = search(arr[0], pattern, suffixArray);
        if (!res.empty())
        {
            std::cout << i << ": ";
//            ss << i << ": ";
            for (int j = 0; j < res.size() - 1; ++j)
            {
                std::cout << res[j] + 1 << ", ";
//                ss << res[j] + 1 << ", ";
            }
            std::cout << res[res.size() - 1] + 1 << "\n";
//            ss << res[res.size() - 1] + 1 << "\n";
        }
    }

    return ss.str();
}

int main()
{

    suffixArrayTask("input.txt");


}