How to split text without spaces into a list of words using dictionary-based segmentation in C

2 Answers

0 votes
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

/*  
    Helper: check if a substring is in the dictionary.
    In C we use a simple array of strings and linear search.
*/
bool dict_contains(const char *candidate, const char **dict, size_t dict_size) {
    for (size_t i = 0; i < dict_size; ++i) {
        if (strcmp(candidate, dict[i]) == 0) {
            return true;
        }
    }
    return false;
}

/*
    This function performs the segmentation and prints the result.
    It contains your original DP logic exactly as before.
*/
void segment_text(const char *text, const char **dict, size_t dict_size) {
    const size_t n = strlen(text);

    /* dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid */
    int *dp = calloc(n + 1, sizeof(int));
    bool *valid = calloc(n + 1, sizeof(bool));

    valid[0] = true; /* empty prefix is valid */

    for (size_t i = 1; i <= n; ++i) {
        valid[i] = false;
        for (size_t j = 0; j < i; ++j) {

            /* Check whether dp[j] contains a valid split point;
               if it does, it means the prefix text[0:j] can be segmented. */
            if (valid[j]) {

                /* Create a lightweight substring representing text[j:i].
                   In C we must allocate a temporary buffer. */
                size_t len = i - j;
                char *candidate = malloc(len + 1);
                memcpy(candidate, text + j, len);
                candidate[len] = '\0';

                /* Convert the string_view to a std::string so it can be checked in the dictionary.
                   Then verify whether this substring is a valid dictionary word. */
                if (dict_contains(candidate, dict, dict_size)) {

                    /* Record that index j is the previous valid split before i.
                       This means text[j:i] is a valid word and dp[j] was valid. */
                    dp[i] = (int)j;
                    valid[i] = true;

                    /* Stop searching for other j values because we already found
                       a valid segmentation ending at i. */
                    free(candidate);
                    break;
                }

                free(candidate);
            }
        }
    }

    /* If dp[n] is not valid, segmentation is impossible */
    if (!valid[n]) {
        printf("No valid segmentation found.\n");
        free(dp);
        free(valid);
        return;
    }

    /* Backtrack to recover words */
    char **words = malloc((n + 1) * sizeof(char *));
    size_t count = 0;

    for (int i = (int)n; i > 0; i = dp[i]) {
        int j = dp[i];
        size_t len = i - j;

        char *w = malloc(len + 1);
        memcpy(w, text + j, len);
        w[len] = '\0';

        words[count++] = w;
    }

    /* Reverse the collected words */
    for (size_t i = 0; i < count / 2; ++i) {
        char *tmp = words[i];
        words[i] = words[count - 1 - i];
        words[count - 1 - i] = tmp;
    }

    /* Print results */
    printf("Segmentation result:\n");
    for (size_t i = 0; i < count; ++i) {
        printf("%s\n", words[i]);
        free(words[i]);
    }

    free(words);
    free(dp);
    free(valid);
}

int main(void) {
    const char *text = "thisisatestfoo";

    /* Example dictionary */
    const char *dict[] = {
        "this", "is", "a", "test", "hello", "world", "foo", "bar"
    };
    const size_t dict_size = sizeof(dict) / sizeof(dict[0]);

    /* Call the segmentation function */
    segment_text(text, dict, dict_size);

    return 0;
}



/*
run:

Segmentation result:
this
is
a
test
foo

*/

 



answered Sep 6 by avibootz
0 votes
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

/*  
    Helper: check if a substring is in the dictionary.
    In C we use a simple array of strings and linear search.
*/
bool dict_contains(const char *candidate, const char **dict, size_t dict_size) {
    for (size_t i = 0; i < dict_size; ++i) {
        if (strcmp(candidate, dict[i]) == 0) {
            return true;
        }
    }
    return false;
}

/*
    This function performs the segmentation and returns the result.
    It contains your original DP logic exactly as before.
*/
char **segment_text(const char *text, const char **dict, size_t dict_size, size_t *out_count) {
    const size_t n = strlen(text);

    /* dp[i] = index j such that text[j:i] is a valid word and dp[j] is valid */
    int *dp = calloc(n + 1, sizeof(int));
    bool *valid = calloc(n + 1, sizeof(bool));

    valid[0] = true; /* empty prefix is valid */

    for (size_t i = 1; i <= n; ++i) {
        valid[i] = false;
        for (size_t j = 0; j < i; ++j) {

            /* Check whether dp[j] contains a valid split point;
               if it does, it means the prefix text[0:j] can be segmented. */
            if (valid[j]) {

                /* Create a lightweight substring representing text[j:i].
                   In C we must allocate a temporary buffer. */
                size_t len = i - j;
                char *candidate = malloc(len + 1);
                memcpy(candidate, text + j, len);
                candidate[len] = '\0';

                /* Convert the string_view to a std::string so it can be checked in the dictionary.
                   Then verify whether this substring is a valid dictionary word. */
                if (dict_contains(candidate, dict, dict_size)) {

                    /* Record that index j is the previous valid split before i.
                       This means text[j:i] is a valid word and dp[j] was valid. */
                    dp[i] = (int)j;
                    valid[i] = true;

                    /* Stop searching for other j values because we already found
                       a valid segmentation ending at i. */
                    free(candidate);
                    break;
                }

                free(candidate);
            }
        }
    }

    /* If dp[n] is not valid, segmentation is impossible */
    if (!valid[n]) {
        free(dp);
        free(valid);
        *out_count = 0;
        return NULL;
    }

    /* Backtrack to recover words */
    char **words = malloc((n + 1) * sizeof(char *));
    size_t count = 0;

    for (int i = (int)n; i > 0; i = dp[i]) {
        int j = dp[i];
        size_t len = i - j;

        char *w = malloc(len + 1);
        memcpy(w, text + j, len);
        w[len] = '\0';

        words[count++] = w;
    }

    /* Reverse the collected words */
    for (size_t i = 0; i < count / 2; ++i) {
        char *tmp = words[i];
        words[i] = words[count - 1 - i];
        words[count - 1 - i] = tmp;
    }

    free(dp);
    free(valid);

    *out_count = count;

    return words;
}

int main(void) {
    const char *text = "thisisatestfoo";

    /* Example dictionary */
    const char *dict[] = {
        "this", "is", "a", "test", "hello", "world", "foo", "bar"
    };
    const size_t dict_size = sizeof(dict) / sizeof(dict[0]);

    /* Call the segmentation function */
    size_t count = 0;
    char **words = segment_text(text, dict, dict_size, &count);

    if (!words) {
        printf("No valid segmentation found.\n");
        return 0;
    }

    /* Print results */
    printf("Segmentation result:\n");
    for (size_t i = 0; i < count; ++i) {
        printf("%s\n", words[i]);
        free(words[i]);
    }

    free(words);
    
    return 0;
}


/*
run:

Segmentation result:
this
is
a
test
foo

*/

 



answered Sep 7 by avibootz

Related questions

...