Longest Common Substring in DSA C - Build from Scratch

Longest Common Substring

📖 Scenario: Imagine you are building a simple text comparison tool. You want to find the longest sequence of characters that appears in both texts exactly the same way. This is useful in spell checkers, plagiarism detectors, or DNA sequence analysis.

🎯 Goal: Build a program in C that finds the longest common substring between two given strings.

📋 What You'll Learn

Create two string variables with exact values

Create an integer variable to store the maximum length found

Use nested loops to compare substrings of both strings

Print the longest common substring found

💡 Why This Matters

🌍 Real World

Finding longest common substrings is useful in text comparison tools, DNA sequence analysis, and plagiarism detection.

💼 Career

Understanding string matching algorithms is important for software developers working on search engines, bioinformatics, and data cleaning.

1

Create the input strings

Create two string variables called str1 and str2 with these exact values: "abcdef" and "zabcf" respectively.

DSA C

char str1[] = "abcdef";
char str2[] = "zabcf";
// Your code here

Hint

Use double quotes to create string arrays in C.

2

Create variables for tracking longest substring

Create an integer variable called max_len and set it to 0. Also create an integer variable called end_index and set it to 0 to track the end position of the longest substring in str1.

DSA C

char str1[] = "abcdef";
char str2[] = "zabcf";
int max_len = 0;
int end_index = 0;
// Your code here

Hint

Use int to declare integer variables in C.

3

Find the longest common substring using nested loops

Use nested for loops with variables i and j to iterate over str1 and str2. Inside, use a while loop with variable length to count matching characters starting at i and j. Update max_len and end_index when a longer substring is found.

DSA C

char str1[] = "abcdef";
char str2[] = "zabcf";
int max_len = 0;
int end_index = 0;

// Your code here

Hint

Use nested loops to check every possible starting point in both strings.

Use a while loop to count matching characters.

4

Print the longest common substring

Print the longest common substring from str1 using max_len and end_index. Use a for loop with variable k to print characters from end_index - max_len + 1 to end_index. Then print a newline.

DSA C

char str1[] = "abcdef";
char str2[] = "zabcf";
int max_len = 0;
int end_index = 0;

for (int i = 0; str1[i] != '\0'; i++) {
    for (int j = 0; str2[j] != '\0'; j++) {
        int length = 0;
        while (str1[i + length] != '\0' && str2[j + length] != '\0' && str1[i + length] == str2[j + length]) {
            length++;
        }
        if (length > max_len) {
            max_len = length;
            end_index = i + length - 1;
        }
    }
}

// Your code here

Hint

Print characters from the start to end of the longest substring using putchar.