94 lines
3.2 KiB
C
94 lines
3.2 KiB
C
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
#include <string.h>
|
|
#include <stdbool.h>
|
|
|
|
|
|
struct Node {
|
|
struct Node* children[10];
|
|
bool isEnd;
|
|
};
|
|
|
|
struct Node* newNode(void) {
|
|
struct Node *nNode = NULL;
|
|
nNode = (struct Node *) malloc(sizeof(struct Node));
|
|
if (nNode) {
|
|
nNode->isEnd = false;
|
|
for (int i = 0; i < 10; i++) {
|
|
nNode->children[i] = NULL;
|
|
}
|
|
}
|
|
return nNode;
|
|
}
|
|
|
|
void free_all(struct Node* node) {
|
|
if (!node) {
|
|
return;
|
|
};
|
|
|
|
for (int i = 0; i < 10; i++) {
|
|
free_all(node->children[i]);
|
|
};
|
|
|
|
free(node);
|
|
}
|
|
|
|
int numbers[] = {11354, 113, 77777, 255044};
|
|
|
|
int main(void) {
|
|
struct Node* root = newNode();
|
|
int n_numbers = sizeof(numbers)/sizeof(int);
|
|
|
|
for (int i = 0; i < n_numbers; i++) { // Go through all the phone numbers in the global list
|
|
struct Node* pointer = root; // Create a pointer that points to whatever part of the trie we're working on
|
|
char number[8 + 1]; // A number has 8 + \0 chars
|
|
snprintf(number, 9, "%i", numbers[i]); // Convert int to string
|
|
int len_number = strlen(number);
|
|
for (int j = 0; j < len_number; j++) { // loop over chars in the phone number
|
|
int index = number[j] - '0'; // Go to the node we're testing
|
|
if (pointer->children[index] == NULL) {
|
|
pointer->children[index] = newNode();
|
|
};
|
|
pointer = pointer->children[index];
|
|
|
|
if (j == len_number - 1) { // if we are at the last iteration
|
|
if (pointer->isEnd == true) { // Check if we've seen the number before
|
|
printf("Duplicate Number found at element %i, number %s", i, number);
|
|
break;
|
|
};
|
|
// if we're at the last iteration, and isEnd isnt true, its either a new number OR we found a prefix
|
|
bool continues = false;
|
|
for (int k = 0; k < 10; k++) {
|
|
if( pointer->children[k] != NULL) {
|
|
continues = true;
|
|
};
|
|
};
|
|
if (continues == true) {
|
|
printf("%s and %s", number, number);
|
|
while (pointer->isEnd != true) { // follow the first path you can find
|
|
for (int k = 0; k < 10; k++) {
|
|
if( pointer->children[k] != NULL) {
|
|
pointer = pointer->children[k];
|
|
printf("%c", k + '0'); // Print the path as we go
|
|
break;
|
|
};
|
|
};
|
|
};
|
|
printf("\n");
|
|
free_all(root); // Clean up
|
|
return 0; // return true or success or whatever
|
|
};
|
|
pointer->isEnd = true;
|
|
}
|
|
else if (pointer->isEnd == true) { // if we've already seen a shorter number with this prefix
|
|
for (int k = 0; k <= j; k++) {
|
|
printf("%c", number[k]);
|
|
}
|
|
printf(" and %i\n", numbers[i]);
|
|
return 0;
|
|
};
|
|
};
|
|
};
|
|
return 1;
|
|
}
|