#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <stdint.h>
void GetLargestCommonSubstring(string & result, const string & a, const string & b)
{
const int a_size = a.size();
const int b_size = b.size();
typedef vector<int> solution;
const int solution_size = b_size + 1;
solution x(solution_size, 0), y(solution_size);
solution * previous = &x;
solution * current = &y;
int max_length = 0;
int result_index = 0;
for(int i = a_size - 1; i >= 0; —i) {
for(int j = b_size - 1; j >= 0; —j) {
int & current_match = (*current)[j];
if(a[i] != b[j]) {
current_match = 0;
}
else {
const int length = 1 + (*previous)[j + 1];
if (length > max_length) {
max_length = length;
result_index = i;
}
current_match = length;
}
}
swap(previous, current);
}
result = a.substr(result_index, max_length);
}
typedef map<char, uint8_t> ValidChars;
void extend(ValidChars & valid, string & s)
{
for (auto i = s.begin(); i != s.end(); ++valid[*i++]);
}
void filter(ValidChars & valid, string & s)
{
s.erase(remove_if(s.begin(), s.end(), [&](char c) -> bool { return !valid.count(c); }), s.end());
}
int main(int argc, char** argv)
{
string x, y, z;
printf « "Enter x: ";
scanf » x;
printf « "Enter y: ";
scanf » y;
ValidChars valid;
extend(valid, x);
extend(valid, y);
for (auto i = valid.begin(); i != valid.end(); i->second > 1 ? ++i : valid.erase(i++));
filter(valid, x);
filter(valid, y);
GetLargestCommonSubstring(z, x, y);
printf « "z: " « z « endl;
return 0;
}