Introduction

The longest common substring problem asks for the longest contiguous sequence of characters shared by two strings. The word contiguous is the key detail: unlike longest common subsequence, you are not allowed to skip characters in the middle.

Dynamic Programming Idea

The standard solution uses dynamic programming. Let dp[i][j] represent the length of the longest common suffix ending at a[i - 1] and b[j - 1]. If the characters match, you extend the previous diagonal value by one. If they do not match, the current suffix length becomes zero because a substring cannot have gaps.

That gives the recurrence:

• if a[i - 1] == b[j - 1], then dp[i][j] = dp[i - 1][j - 1] + 1
• otherwise dp[i][j] = 0

While filling the table, you also track the best length found so far and where it ends in the first string.

A Runnable C Implementation

The following program computes the longest common substring and prints it. It uses dynamic allocation for the table and copies the resulting substring into a newly allocated output buffer.

1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5char *longest_common_substring(const char *a, const char *b) {
6    size_t len_a = strlen(a);
7    size_t len_b = strlen(b);
8
9    size_t rows = len_a + 1;
10    size_t cols = len_b + 1;
11
12    int *dp = calloc(rows * cols, sizeof(int));
13    if (dp == NULL) {
14        return NULL;
15    }
16
17    size_t best_length = 0;
18    size_t best_end = 0;
19
20    for (size_t i = 1; i <= len_a; i++) {
21        for (size_t j = 1; j <= len_b; j++) {
22            if (a[i - 1] == b[j - 1]) {
23                int value = dp[(i - 1) * cols + (j - 1)] + 1;
24                dp[i * cols + j] = value;
25
26                if ((size_t)value > best_length) {
27                    best_length = (size_t)value;
28                    best_end = i;
29                }
30            } else {
31                dp[i * cols + j] = 0;
32            }
33        }
34    }
35
36    char *result = malloc(best_length + 1);
37    if (result == NULL) {
38        free(dp);
39        return NULL;
40    }
41
42    memcpy(result, a + best_end - best_length, best_length);
43    result[best_length] = '\0';
44
45    free(dp);
46    return result;
47}
48
49int main(void) {
50    const char *first = "bananarama";
51    const char *second = "anatomy";
52
53    char *answer = longest_common_substring(first, second);
54    if (answer == NULL) {
55        fprintf(stderr, "allocation failed\n");
56        return 1;
57    }
58
59    printf("Longest common substring: %s\n", answer);
60    free(answer);
61    return 0;
62}

For these inputs, the output is ana.

Why the Reset to Zero Matters

The zero on mismatch is what makes this a substring algorithm rather than a subsequence algorithm. If you reused a value from the left or top cell on mismatch, you would be allowing gaps, which changes the problem completely.

That is why the table stores common suffix lengths rather than arbitrary best values. Every cell answers a very narrow question: how long is the matching run ending exactly here? Once you think about it that way, the recurrence becomes natural.

Space Optimization

The full table uses O(m * n) time and O(m * n) memory for strings of lengths m and n. For moderate inputs that is fine, but for large strings the memory cost can become significant.

You can reduce memory to O(n) by keeping only the previous row and the current row, because each cell depends only on the diagonal value from the previous row. The logic stays the same, but you store fewer intermediate values.

1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5size_t longest_common_substring_length(const char *a, const char *b) {
6    size_t len_a = strlen(a);
7    size_t len_b = strlen(b);
8    int *previous = calloc(len_b + 1, sizeof(int));
9    int *current = calloc(len_b + 1, sizeof(int));
10    size_t best = 0;
11
12    if (previous == NULL || current == NULL) {
13        free(previous);
14        free(current);
15        return 0;
16    }
17
18    for (size_t i = 1; i <= len_a; i++) {
19        for (size_t j = 1; j <= len_b; j++) {
20            if (a[i - 1] == b[j - 1]) {
21                current[j] = previous[j - 1] + 1;
22                if ((size_t)current[j] > best) {
23                    best = (size_t)current[j];
24                }
25            } else {
26                current[j] = 0;
27            }
28        }
29
30        int *temp = previous;
31        previous = current;
32        current = temp;
33        memset(current, 0, (len_b + 1) * sizeof(int));
34    }
35
36    free(previous);
37    free(current);
38    return best;
39}

This version returns only the length, which is often enough when you care about scoring similarity rather than reconstructing the substring itself.

Common Pitfalls

• Confusing longest common substring with longest common subsequence.
• Forgetting to reset the DP cell to zero on mismatch.
• Tracking only the maximum length and not the end position needed to extract the answer.
• Allocating a full matrix for very large strings without considering memory use.
• Forgetting to free the dynamically allocated result or DP buffers.

Summary

• Longest common substring requires consecutive matching characters.
• Dynamic programming solves it cleanly in O(m * n) time.
• Each DP cell stores the length of a matching suffix ending at a specific pair of positions.
• Track both best length and best end index if you need the substring itself.
• Use a rolling-row optimization when memory matters more than reconstructing the full table.