#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
/*
removeDuplicateWordsFreeText (C version)
Removes duplicate words from free text:
- Case‑insensitive comparison
- Preserves original casing of first occurrence
- Splits on ANY non‑letter sequence
- Preserves original order
- Efficient O(n) using a simple hash set
Strategy:
1. Trim outer whitespace.
2. Split on ANY non‑letter sequence using manual scanning.
3. Lowercase each word for comparison.
4. Keep only first occurrence.
5. Reassemble into a space‑separated string.
*/
/* ---------------------------------------------------------------
Trim whitespace from both ends
--------------------------------------------------------------- */
char *trim(char *s) {
while (isspace((unsigned char)*s)) s++;
if (*s == 0) return s;
char *end = s + strlen(s) - 1;
while (end > s && isspace((unsigned char)*end)) end--;
end[1] = '\0';
return s;
}
/* ---------------------------------------------------------------
Convert string to lowercase (copy)
--------------------------------------------------------------- */
char *toLowerCopy(const char *s) {
size_t len = strlen(s);
char *out = malloc(len + 1);
for (size_t i = 0; i < len; i++)
out[i] = tolower((unsigned char)s[i]);
out[len] = '\0';
return out;
}
/* ---------------------------------------------------------------
Simple hash set for strings (open addressing)
--------------------------------------------------------------- */
typedef struct {
char **keys;
size_t size;
} HashSet;
size_t hashString(const char *s, size_t size) {
size_t h = 146527;
while (*s) h = h * 33 ^ (unsigned char)*s++;
return h % size;
}
HashSet *hashSetCreate(size_t size) {
HashSet *set = malloc(sizeof(HashSet));
set->size = size;
set->keys = calloc(size, sizeof(char *));
return set;
}
int hashSetInsert(HashSet *set, const char *key) {
size_t idx = hashString(key, set->size);
for (size_t i = 0; i < set->size; i++) {
size_t pos = (idx + i) % set->size;
if (set->keys[pos] == NULL) {
set->keys[pos] = strdup(key);
return 1; // inserted
}
if (strcmp(set->keys[pos], key) == 0)
return 0; // duplicate
}
return 0;
}
void hashSetFree(HashSet *set) {
for (size_t i = 0; i < set->size; i++)
free(set->keys[i]);
free(set->keys);
free(set);
}
/* ---------------------------------------------------------------
Split free text into words using ANY non‑letter sequence
--------------------------------------------------------------- */
char **splitWords(const char *text, int *count) {
char *copy = strdup(text);
char *p = copy;
char **words = malloc(sizeof(char *) * 1024);
int wcount = 0;
while (*p) {
while (*p && !isalpha((unsigned char)*p)) p++;
if (!*p) break;
char *start = p;
while (*p && isalpha((unsigned char)*p)) p++;
size_t len = p - start;
char *word = malloc(len + 1);
memcpy(word, start, len);
word[len] = '\0';
words[wcount++] = word;
}
free(copy);
*count = wcount;
return words;
}
/* ---------------------------------------------------------------
Remove duplicates (case‑insensitive)
--------------------------------------------------------------- */
char *removeDuplicateWordsFreeText(const char *text) {
char *clean = trim(strdup(text));
int count = 0;
char **words = splitWords(clean, &count);
HashSet *seen = hashSetCreate(2048);
char **unique = malloc(sizeof(char *) * count);
int ucount = 0;
for (int i = 0; i < count; i++) {
char *lower = toLowerCopy(words[i]);
if (hashSetInsert(seen, lower)) {
unique[ucount++] = words[i]; // preserve original casing
} else {
free(words[i]);
}
free(lower);
}
// Build output string
size_t total = 0;
for (int i = 0; i < ucount; i++)
total += strlen(unique[i]) + 1;
char *result = malloc(total + 1);
result[0] = '\0';
for (int i = 0; i < ucount; i++) {
strcat(result, unique[i]);
if (i + 1 < ucount) strcat(result, " ");
free(unique[i]);
}
free(unique);
free(words);
free(clean);
hashSetFree(seen);
return result;
}
/* ---------------------------------------------------------------
Main
--------------------------------------------------------------- */
int main() {
const char *input =
"Hello, hello! This is a test. A TEST, hello universe... "
"UNIVERSE! Hello; *** Is Anybody There?";
char *output = removeDuplicateWordsFreeText(input);
printf("%s\n", output);
free(output);
return 0;
}
/*
run:
Hello This is a test universe Anybody There
*/