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:

Go to the source code of this file.

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

Definition in file longest_common_string.cpp.

Function Documentation

get_test_cases()

std::vector< TestCase > get_test_cases

(

)

Returns

example data used in the tests of longest_common_string_length

Definition at line 69 of file longest_common_string.cpp.

                                     {
    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

Definition at line 28 of file longest_common_string.cpp.

                                                                    {
    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];
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 156 of file longest_common_string.cpp.

           {
    tests();
    return 0;
}

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

Definition at line 119 of file longest_common_string.cpp.

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

test_longest_common_string_length()

template<typename TestCases>

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

Definition at line 91 of file longest_common_string.cpp.

                                                                           {
    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);
    }
}

test_longest_common_string_length_for_reversed_inputs()

template<typename TestCases>

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

Definition at line 130 of file longest_common_string.cpp.

                                 {
    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);
    }
}

test_longest_common_string_length_is_symmetric()

template<typename TestCases>

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

Definition at line 105 of file longest_common_string.cpp.

                                 {
    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);
    }
}

tests()

void tests ( )

static

runs all tests for longest_common_string_length funcion

Definition at line 142 of file longest_common_string.cpp.

                    {
    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";
}