longest_common_string.cpp File Reference

contains the definition of the function longest_common_string_length More...

#include <cassert>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

Include dependency graph for longest_common_string.cpp:

Classes
struct	TestCase
	represents single example inputs and expected output of the function longest_common_string_length More...

Functions
std::size_t	longest_common_string_length (const std::string &string_a, const std::string &string_b)
	computes the length of the longest common string created from input strings
std::vector< TestCase >	get_test_cases ()
template<typename TestCases >
static void	test_longest_common_string_length (const TestCases &test_cases)
	checks the function longest_common_string_length agains example data
template<typename TestCases >
static void	test_longest_common_string_length_is_symmetric (const TestCases &test_cases)
	checks if the function longest_common_string_length returns the same result when its argument are flipped
std::string	reverse_str (const std::string &in_str)
	reverses a given string
template<typename TestCases >
static void	test_longest_common_string_length_for_reversed_inputs (const TestCases &test_cases)
	checks if the function longest_common_string_length returns the same result when its inputs are reversed
static void	tests ()
	runs all tests for longest_common_string_length funcion
int	main ()
	Main function.

Detailed Description

contains the definition of the function longest_common_string_length

the function longest_common_string_length computes the length of the longest common string which can be created of two input strings by removing characters from them

Author

Nikhil Arora

Piotr Idzik

Function Documentation

get_test_cases()

std::vector< TestCase > get_test_cases

(

)

Returns

example data used in the tests of longest_common_string_length

                                     {
    return {TestCase("", "", 0),
            TestCase("ab", "ab", 2),
            TestCase("ab", "ba", 1),
            TestCase("", "xyz", 0),
            TestCase("abcde", "ace", 3),
            TestCase("BADANA", "ANADA", 3),
            TestCase("BADANA", "CANADAS", 3),
            TestCase("a1a234a5aaaa6", "A1AAAA234AAA56AAAAA", 6),
            TestCase("123x", "123", 3),
            TestCase("12x3x", "123", 3),
            TestCase("1x2x3x", "123", 3),
            TestCase("x1x2x3x", "123", 3),
            TestCase("x12x3x", "123", 3)};
}

longest_common_string_length()

std::size_t longest_common_string_length	(	const std::string &	string_a,
		const std::string &	string_b )

computes the length of the longest common string created from input strings

for assert for std::cout for std::string for std::move for std::vector

has O(str_a.size()*str_b.size()) time and memory complexity

Parameters

string_a	first input string
string_b	second input string

Returns

the length of the longest common string which can be strated from str_a and str_b

                                                                    {
    const auto size_a = string_a.size();
    const auto size_b = string_b.size();
    std::vector<std::vector<std::size_t>> sub_sols(
        size_a + 1, std::vector<std::size_t>(size_b + 1, 0));
 
    const auto limit = static_cast<std::size_t>(-1);
    for (std::size_t pos_a = size_a - 1; pos_a != limit; --pos_a) {
        for (std::size_t pos_b = size_b - 1; pos_b != limit; --pos_b) {
            if (string_a[pos_a] == string_b[pos_b]) {
                sub_sols[pos_a][pos_b] = 1 + sub_sols[pos_a + 1][pos_b + 1];
            } else {
                sub_sols[pos_a][pos_b] = std::max(sub_sols[pos_a + 1][pos_b],
                                                  sub_sols[pos_a][pos_b + 1]);
            }
        }
    }
 
    return sub_sols[0][0];
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    tests();
    return 0;
}

Here is the call graph for this function:

reverse_str()

std::string reverse_str

(

const std::string &

in_str

)

reverses a given string

Parameters

in_str

input string

Returns

the string in which the characters appear in the reversed order as in in_str

                                               {
    return {in_str.rbegin(), in_str.rend()};
}

Here is the call graph for this function:

test_longest_common_string_length()

template<typename TestCases >

static void test_longest_common_string_length ( const TestCases & test_cases )

static

checks the function longest_common_string_length agains example data

Parameters

test_cases

list of test cases

Template Parameters

type	representing a list of test cases

                                                                           {
    for (const auto& cur_tc : test_cases) {
        assert(longest_common_string_length(cur_tc.string_a, cur_tc.string_b) ==
               cur_tc.common_string_len);
    }
}

Here is the call graph for this function:

test_longest_common_string_length_for_reversed_inputs()

template<typename TestCases >

static void test_longest_common_string_length_for_reversed_inputs ( const TestCases & test_cases )

static

checks if the function longest_common_string_length returns the same result when its inputs are reversed

Parameters

test_cases

list of test cases

Template Parameters

type	representing a list of test cases

                                 {
    for (const auto& cur_tc : test_cases) {
        assert(longest_common_string_length(reverse_str(cur_tc.string_a),
                                            reverse_str(cur_tc.string_b)) ==
               cur_tc.common_string_len);
    }
}

Here is the call graph for this function:

test_longest_common_string_length_is_symmetric()

template<typename TestCases >

static void test_longest_common_string_length_is_symmetric ( const TestCases & test_cases )

static

checks if the function longest_common_string_length returns the same result when its argument are flipped

Parameters

test_cases

list of test cases

Template Parameters

type	representing a list of test cases

                                 {
    for (const auto& cur_tc : test_cases) {
        assert(longest_common_string_length(cur_tc.string_b, cur_tc.string_a) ==
               cur_tc.common_string_len);
    }
}

Here is the call graph for this function:

tests()

static void tests ( )

static

runs all tests for longest_common_string_length funcion

                    {
    const auto test_cases = get_test_cases();
    assert(test_cases.size() > 0);
    test_longest_common_string_length(test_cases);
    test_longest_common_string_length_is_symmetric(test_cases);
    test_longest_common_string_length_for_reversed_inputs(test_cases);
 
    std::cout << "All tests have successfully passed!\n";
}

Here is the call graph for this function: