Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/da/d0d/longest__common__string_8cpp.html below:

TheAlgorithms/C++: dynamic_programming/longest_common_string.cpp File Reference

Loading...

Searching...

No Matches

contains the definition of the function longest_common_string_length More...

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

Go to the source code of this file.

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

Definition in file longest_common_string.cpp.

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.

29 {

30 const auto size_a = string_a.size();

31 const auto size_b = string_b.size();

32 std::vector<std::vector<std::size_t>> sub_sols(

33 size_a + 1, std::vector<std::size_t>(size_b + 1, 0));

34

35 const auto limit = static_cast<std::size_t>(-1);

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 function.

Returns

0 on exit

Definition at line 156 of file longest_common_string.cpp.

156 {

158 return 0;

159}

static void tests()

runs all tests for longest_common_string_length funcion

reverses a given string

Parameters

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.

119 {

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

121}

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.

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

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.

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

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.

106 {

107 for (const auto& cur_tc : test_cases) {

109 cur_tc.common_string_len);

110 }

111}

runs all tests for longest_common_string_length funcion

Definition at line 142 of file longest_common_string.cpp.

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...

std::vector< TestCase > get_test_cases()

static void test_longest_common_string_length(const TestCases &test_cases)

checks the function longest_common_string_length agains example data

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...

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4