Question

How to find the longest common prefix of all the words in a string with C

Answer 1

#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAX_WORDS 64
#define MAX_LEN   128

// Extract lowercase words from a string
int extract_words(const char *s, char words[][MAX_LEN]) {
    int count = 0, i = 0, j = 0;

    while (s[i]) {
        if (isalpha(s[i])) {
            j = 0;
            while (isalpha(s[i])) {
                words[count][j++] = tolower(s[i++]);
            }
            words[count][j] = '\0';
            count++;
        } else {
            i++;
        }
    }
    return count;
}

// Longest common prefix of two strings
void lcp_two(const char *a, const char *b, char *out) {
    int i = 0;
    while (a[i] && b[i] && a[i] == b[i]) {
        out[i] = a[i];
        i++;
    }
    out[i] = '\0';
}

// LCP of all words
void longest_common_prefix(const char *s, char *result) {
    char words[MAX_WORDS][MAX_LEN];
    int n = extract_words(s, words);

    if (n == 0) {
        result[0] = '\0';
        return;
    }

    strcpy(result, words[0]);

    char temp[MAX_LEN];
    for (int i = 1; i < n; i++) {
        lcp_two(result, words[i], temp);
        strcpy(result, temp);
        if (result[0] == '\0') return;
    }
}

int main() {
    char result[MAX_LEN];

    char s1[] = "The lowly inhabitants of the lowland were surprised to see the lower branches.";
    longest_common_prefix(s1, result);
    printf("LCP: '%s'\n", result);   // prints ""

    char s2[] = "unclear uncertain unexpected";
    longest_common_prefix(s2, result);
    printf("LCP: '%s'\n", result);   // prints "un"
}



/*
run:

LCP: ''
LCP: 'un'

*/

 

70+ SQL courses for beginners and professionals