contains the definition of the function longest_common_string_length
More...
#include <cassert>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
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
◆ get_test_cases()
- Returns
- example data used in the tests of longest_common_string_length
69 {
77 TestCase(
"a1a234a5aaaa6",
"A1AAAA234AAA56AAAAA", 6),
83}
represents single example inputs and expected output of the function longest_common_string_length
Definition longest_common_string.cpp:54
◆ longest_common_string_length()
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
29 {
30 const auto size_a = string_a.
size();
31 const auto size_b = string_b.
size();
34
36 for (
std::size_t pos_a = size_a - 1; pos_a != limit; --pos_a) {
37 for (
std::size_t pos_b = size_b - 1; pos_b != limit; --pos_b) {
38 if (string_a[pos_a] == string_b[pos_b]) {
39 sub_sols[pos_a][pos_b] = 1 + sub_sols[pos_a + 1][pos_b + 1];
40 } else {
41 sub_sols[pos_a][pos_b] =
std::max(sub_sols[pos_a + 1][pos_b],
42 sub_sols[pos_a][pos_b + 1]);
43 }
44 }
45 }
46
47 return sub_sols[0][0];
48}
◆ main()
Main function.
- Returns
- 0 on exit
156 {
158 return 0;
159}
static void tests()
runs all tests for longest_common_string_length funcion
Definition longest_common_string.cpp:142
◆ reverse_str()
reverses a given string
- Parameters
-
- Returns
- the string in which the characters appear in the reversed order as in in_str
◆ test_longest_common_string_length()
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 |
91 {
92 for (const auto& cur_tc : test_cases) {
94 cur_tc.common_string_len);
95 }
96}
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
Definition longest_common_string.cpp:28
◆ test_longest_common_string_length_for_reversed_inputs()
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 |
131 {
132 for (const auto& cur_tc : test_cases) {
135 cur_tc.common_string_len);
136 }
137}
std::string reverse_str(const std::string &in_str)
reverses a given string
Definition longest_common_string.cpp:119
◆ test_longest_common_string_length_is_symmetric()
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 |
106 {
107 for (const auto& cur_tc : test_cases) {
109 cur_tc.common_string_len);
110 }
111}
◆ tests()
runs all tests for longest_common_string_length funcion
142 {
144 assert(test_cases.size() > 0);
148
149 std::cout <<
"All tests have successfully passed!\n";
150}
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 rever...
Definition longest_common_string.cpp:130
std::vector< TestCase > get_test_cases()
Definition longest_common_string.cpp:69
static void test_longest_common_string_length(const TestCases &test_cases)
checks the function longest_common_string_length agains example data
Definition longest_common_string.cpp:91
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 fli...
Definition longest_common_string.cpp:105