Python Challenge | Longest Common Substring

Introduction

This Python challenge is about finding the longest common substring between two given strings.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ModulesandPackagesGroup(["`Modules and Packages`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/ErrorandExceptionHandlingGroup(["`Error and Exception Handling`"]) python/BasicConceptsGroup -.-> python/comments("`Comments`") algorithm/BasicAlgorithmsGroup -.-> algorithm/arrays_strings("`Arrays Strings`") python/BasicConceptsGroup -.-> python/variables_data_types("`Variables and Data Types`") python/BasicConceptsGroup -.-> python/strings("`Strings`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/for_loops("`For Loops`") python/ControlFlowGroup -.-> python/while_loops("`While Loops`") python/ControlFlowGroup -.-> python/list_comprehensions("`List Comprehensions`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/ModulesandPackagesGroup -.-> python/standard_libraries("`Common Standard Libraries`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/ErrorandExceptionHandlingGroup -.-> python/raising_exceptions("`Raising Exceptions`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills python/comments -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} algorithm/arrays_strings -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/variables_data_types -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/strings -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/conditional_statements -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/for_loops -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/while_loops -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/list_comprehensions -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/lists -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/tuples -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/function_definition -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/standard_libraries -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/classes_objects -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/encapsulation -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/raising_exceptions -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} python/build_in_functions -.-> lab-268865{{"`Python Challenge: Longest Common Substring`"}} end

Longest Substring

Problem

Given two strings, the task is to find the longest common substring. A substring is a contiguous block of characters. The solution should be case-sensitive and assume that the strings are ASCII. The output should be a string and the program should assume that the inputs are not necessarily valid. However, it can assume that the problem fits in memory.

Requirements

To solve this problem, the program must meet the following requirements:

The inputs are not necessarily valid.

The strings are ASCII.

The solution should be case-sensitive.

A substring is a contiguous block of characters.

The output should be a string.

The program should assume that the problem fits in memory.

Example Usage

The program should behave as follows:

If str0 or str1 is None, an exception should be raised.

If str0 or str1 equals 0, the output should be an empty string.

In the general case, given str0 = 'ABCDEFGHIJ' and str1 = 'FOOBCDBCDE', the output should be 'BCDE'.

Summary

This Python challenge required finding the longest common substring between two given strings. The program should assume that the inputs are not necessarily valid, but that the problem fits in memory. The solution should be case-sensitive and assume that the strings are ASCII. The output should be a string.

Python Challenge: Longest Common Substring