lrss.cpp

#include <vector>
#include <iostream>
#include <string>
#include <algorithm>

unsigned int sharedPrefixLength(const char *a, const char *b);
std::string longestRepeatedString(const std::string s);

int main()
{
    std::string s;
    std::getline(std::cin, s);

    std::cout << "Longest repeated string:\n“"
        << longestRepeatedString(s) << "”" << std::endl;

    return 0;
}

unsigned int sharedPrefixLength(const char *a, const char *b)
{
    int len = 0;
    while (*a != '\0' && *b != '\0' && *a == *b) {
        ++a, ++b, ++len;
    }

    return len;
}

std::string longestRepeatedString(const std::string s)
{
    std::vector<const char*> suffixes;

    // generate a suffix array
    for (int i = 0; i < s.length(); ++i) {
        suffixes.push_back(&s.at(i));
    }

    // sort the suffix array
    std::sort(suffixes.begin(), suffixes.end(),
            [](const char *a, const char *b) {
                // compare until we find a difference (or reach an end)
                while (*a != '\0' && *b != '\0' && *a == *b) {
                    a++, b++;
                }
                return *b > *a;
            });

    // pairwise compare the sorted suffixes to find the longest repeated one
    const char *longestFound = nullptr;
    int maxLength = 0;
    for (int i = 0; i < suffixes.size()-1; ++i) {
        int len = sharedPrefixLength(suffixes[i], suffixes[i+1]);

        if (len > maxLength) {
            maxLength = len;
            longestFound = suffixes[i];
        }
    }

    return std::string(longestFound, maxLength);
}