#include<iostream>
#include <vector>
using namespace std;

void GetLargestCommonSubstring(const char a[], const char [] b, char res[]) {
    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);
}


int main(){
    char result[100];

    const char str1[] = "djhgkjfdjklgjdfjkglasd1234";
    const char str2[] = "lgjdf39485093849058jklkdjf";
    GetLargestCommonSubstring(str1, str2,result);
    cout<<result;

    return 0;
}