powercoderlol · Feb 8, 2019 · Mar 30, 2018 · Mar 30, 2018 · Apr 1, 2018 · Feb 8, 2019
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,40 @@
+#ignore thumbnails created by windows
+Thumbs.db
+#Ignore files build by Visual Studio
+*.obj
+*.exe
+*.pdb
+*.user
+*.aps
+*.pch
+*.vspscc
+*_i.c
+*_p.c
+*.ncb
+*.suo
+*.tlb
+*.tlh
+*.bak
+*.cache
+*.orig
+*.ilk
+*.log
+[Bb]in
+[Dd]ebug*/
+*.lib
+*.sbr
+obj/
+[Rr]elease*/
+_ReSharper*/
+[Tt]est[Rr]esult*
+*.ipch
+*.sdf
+*.opensdf
+*.idb
+*.zip
+autodata/
+log/
+build/
+.idea/
+cmake-build*/
+.idea/
diff --git a/.travis.yml b/.travis.yml
@@ -1,5 +1,5 @@
-dist:     trusty    # используем Ubuntu 14.04 Trusty Tahr (а не 12.02 Precise Pangolin)
-sudo:     required  # используем Virtual Machine (а не Docker container)
+dist:     xenial    
+sudo:     required  
 
 language: cpp
 
@@ -32,7 +32,17 @@ matrix:
 
 
 script:
+    - cmake --version
     - mkdir build
     - cd build
     - cmake .. -DCMAKE_BUILD_TYPE=$BUILD_CONFIGURATION -DTARGET_CPU=$TARGET_CPU
     - cmake --build .
+    - ctest -C Debug
+    - ctest -C Release
+
+
+after_script:
+    - uname --all
+    - env
+    - pwd
+    - ls -la
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -1,7 +1,61 @@
 project(algorithms)
 cmake_minimum_required(VERSION 2.8.11)
 
-set(SOURCES LongestSubstring.cpp)
+set(CMAKE_MODULE_PATH ${CMAKE_MODULE_PATH} ${PROJECT_SOURCE_DIR})
+
+set(CMAKE_CXX_STANDARD 11)
+
+message(STATUS "cmake module path: ${CMAKE_MODULE_PATH}")
+
+# download and unpack googletest at configure time
+configure_file(CMakeLists.txt.in googletest-download/CMakeLists.txt)
+
+execute_process(COMMAND ${CMAKE_COMMAND} -G "${CMAKE_GENERATOR}" .
+  RESULT_VARIABLE    result
+  WORKING_DIRECTORY  ${CMAKE_BINARY_DIR}/googletest-download)
+
+if(result)
+    message(FATAL_ERROR "CMake step for googletest failed: ${result}")
+endif()
+
+execute_process(COMMAND ${CMAKE_COMMAND} --build .
+  RESULT_VARIABLE result
+  WORKING_DIRECTORY ${CMAKE_BINARY_DIR}/googletest-download )
+if(result)
+  message(FATAL_ERROR "Build step for googletest failed: ${result}")
+endif()
+
+set(gtest_force_shared_crt ON CACHE BOOL "" FORCE)
+
+add_subdirectory("${CMAKE_BINARY_DIR}/googletest-src" "${CMAKE_BINARY_DIR}/googletest-build")
+
+if (CMAKE_VERSION VERSION_LESS 2.8.11)
+  include_directories("${gtest_SOURCE_DIR}/include")
+endif()
+
+enable_testing()
+
+include(Sources)
+
+add_library(algorithms_on_strings STATIC ${ALGORITHMS_ON_STRINGS_LIB_SRC})
+target_include_directories(algorithms_on_strings
+  PUBLIC
+  algorithms_on_strings/longest_common_substring)
+
+SET(GTEST_LIBS gtest gtest_main)
+SET(STRING_ALGO_LIBS algorithms_on_strings)
+
+add_library(sorting_algorithms STATIC ${SORTING_ALGORITHMS_LIB_SRC})
+target_include_directories(sorting_algorithms
+  PUBLIC
+  sorting_algorithms/quick_sort)
+set_property(TARGET sorting_algorithms PROPERTY LINKER_LANGUAGE CXX)
+
+SET(SORTING_ALGO_LIBS sorting_algorithms)
+
+add_executable(smoke-test-longest-substring tests/smoke-test-longest-substring.cpp)
+target_link_libraries(smoke-test-longest-substring ${GTEST_LIBS} ${STRING_ALGO_LIBS} ${SORTING_ALGO_LIBS})
+
+add_test(NAME longest-substring-test COMMAND smoke-test-longest-substring)
 
-add_executable(algorithms ${SOURCES})
 
diff --git a/CMakeLists.txt.in b/CMakeLists.txt.in
@@ -0,0 +1,15 @@
+cmake_minimum_required(VERSION 2.8.12)
+
+project(googletest-download NONE)
+
+include(ExternalProject)
+ExternalProject_Add(googletest
+  GIT_REPOSITORY     https://github.com/google/googletest.git
+  GIT_TAG            master
+  SOURCE_DIR         "${CMAKE_BINARY_DIR}/googletest-src"
+  BINARY_DIR         "${CMAKE_BINARY_DIR}/googletest-build"
+  CONFIGURE_COMMAND  ""
+  BUILD_COMMAND      ""
+  INSTALL_COMMAND    ""
+  TEST_COMMAND       ""
+)
diff --git a/LongestSubstring.cpp b/LongestSubstring.cpp
diff --git a/Sources.cmake b/Sources.cmake
@@ -0,0 +1,9 @@
+set(ALGORITHMS_ON_STRINGS_LIB_SRC
+  algorithms_on_strings/longest_common_substring/LongestSubstring.cpp
+  algorithms_on_strings/longest_common_substring/LongestSubstring.h
+)
+
+set(SORTING_ALGORITHMS_LIB_SRC
+  sorting_algorithms/quick_sort/qsort_test.cpp
+  sorting_algorithms/quick_sort/template_qsort.h
+)
diff --git a/algorithms_on_strings/longest_common_substring/LongestSubstring.cpp b/algorithms_on_strings/longest_common_substring/LongestSubstring.cpp
@@ -0,0 +1,12 @@
+#include "LongestSubstring.h"
+
+int main() {
+    char str[30], str1[30], str2[30];
+    scanf("%s", str);
+    scanf("%s", str1);
+
+    findLongestSubstring(str, str1, str2);
+    printf("%s\n", str2);
+
+    return 0;
+}
diff --git a/algorithms_on_strings/longest_common_substring/LongestSubstring.h b/algorithms_on_strings/longest_common_substring/LongestSubstring.h
@@ -0,0 +1,53 @@
+#pragma once
+#include <stdio.h>
+#include <stdlib.h>
+
+void findLongestSubstring(const char a[], const char b[], char res[]) {
+    size_t i, j, k, len_a, len_b, substr_i, max_substr;
+    size_t** matrix;
+
+    for(i = 0; a[i] != '\0'; i++);
+    len_a = i;
+
+    for(j = 0; b[j] != '\0'; j++);
+    len_b = j;
+
+    matrix = (size_t**)malloc((len_a + 1) * sizeof(size_t*));
+
+    for(i = 0; i < len_a; i++) {
+        matrix[i] = (size_t*)malloc((len_b + 1) * sizeof(size_t));
+        for(j = 0; j < len_b; j++) {
+            matrix[i][j] = 0;
+        }
+    }
+    printf("\n");
+
+    max_substr = 0;
+    substr_i = 0;
+
+    for(i = 0; i < len_a; i++) {
+        for(j = 0; j < len_b; j++) {
+            if(a[i] == b[j]) {
+                if((0 == i) || (0 == j))
+                    matrix[i][j] = 1;
+                else
+                    matrix[i][j] = matrix[i - 1][j - 1] + 1;
+                if(matrix[i][j] > max_substr) {
+                    max_substr = matrix[i][j];
+                    substr_i = i;
+                }
+                else if(matrix[i][j] == max_substr)
+                    substr_i = i;
+            }
+            else
+                matrix[i][j] = 0;
+        }
+    }
+
+    k = 0;
+    for(i = (substr_i - max_substr + 1); i <= substr_i; i++) {
+        res[k] = a[i];
+        k++;
+    }
+    res[k] = '\0';
+}
diff --git a/sorting_algorithms/quick_sort/qsort_test.cpp b/sorting_algorithms/quick_sort/qsort_test.cpp
@@ -0,0 +1,6 @@
+#include "template_qsort.h"
+
+int main() {
+    std::array<uint32_t, 10> arr{ 14, 1, 5, 16, 2, 16, 2, 2, 14, 10 };
+	qsort_v1<arr.size()>(arr, 0, arr.size()-1);
+}
diff --git a/sorting_algorithms/quick_sort/template_qsort.h b/sorting_algorithms/quick_sort/template_qsort.h
@@ -0,0 +1,45 @@
+#pragma once
+/*
+ *
+ * Qsort Avrora implementation according to cormen description with
+ * little comparation changes
+ *
+ */
+#include <array>
+#include <cstdint>
+
+void swap_v1(uint32_t& x, uint32_t& y) {
+	uint32_t tmp = y;
+	y = x;
+	x = tmp;
+}
+
+template<std::size_t SIZE>
+unsigned int partition_v1(
+    std::array<uint32_t, SIZE>& arr, unsigned int p, unsigned int r) {
+    auto x = arr[p];
+    auto i = p;
+    auto j = r;
+    while(true) {
+        while(arr[i] < x)
+            i++;
+        while(arr[j] > x)
+            j--;
+        if(i <= j) {
+            swap_v1(arr[i], arr[j]);
+            i++;
+            j--;
+        }
+        else
+            return j;
+    }
+}
+
+template<std::size_t SIZE>
+void qsort_v1(std::array<uint32_t, SIZE>& arr, unsigned int p, unsigned int r) {
+    if(p < r) {
+        auto q = partition_v1<SIZE>(arr, p, r);
+        qsort_v1<SIZE>(arr, p, q);
+        qsort_v1<SIZE>(arr, q + 1, r);
+    }
+}
diff --git a/tests/smoke-test-longest-substring.cpp b/tests/smoke-test-longest-substring.cpp
@@ -0,0 +1,17 @@
+#include <string>
+#include "LongestSubstring.h"
+#include "template_qsort.h"
+
+#include "gtest/gtest.h"
+
+TEST(SimpleSmokeTest, Positive) {
+    char str[30] = "qwerty";
+    char str1[30] = "tyqwe";
+    char str2[30];
+    std::string answer;
+    findLongestSubstring(str, str1, str2);
+
+    answer = str2;
+
+    EXPECT_EQ("qwe", answer);
+}