#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
*/