Skip to content

Instantly share code, notes, and snippets.

@dgodfrey206
Created November 15, 2013 21:54
Show Gist options
  • Save dgodfrey206/7492301 to your computer and use it in GitHub Desktop.
Save dgodfrey206/7492301 to your computer and use it in GitHub Desktop.
A function that finds the largest lexographically-increasing substring in a string.
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>
std::string longest_alpha_substr(const std::string& str)
{
char last = str[0];
int size = 1;
unsigned int i = 1;
std::vector<std::pair<int, int>> pairs;
for (; i < str.size(); ++i)
{
if (str[i] >= last)
{
last = str[i];
++size;
} else
{
pairs.push_back(std::make_pair(i - size, size));
size = 1;
last = str[i];
}
}
pairs.push_back(std::make_pair(i - size, size));
using pair_type = std::pair<int, int>;
auto max = std::max_element(pairs.begin(), pairs.end(), [] (const pair_type& p1, const pair_type& p2)
{
return p1.second < p2.second;
});
return str.substr(max->first, max->second);
}
int main()
{
std::string str = "ghijklmnopqdefghijabcdefghi";
std::cout << longest_alpha_substr(str);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment