Три — найти самый длинный общий префикс

Я хочу найти самый длинный общий префикс в три. Вот мой код:

using namespace std;
#define ALPHABET_SIZE (26)
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')

struct TrieNode{
struct TrieNode *children[ALPHABET_SIZE];
bool isLeaf;
};

struct TrieNode *getNode(void) {
struct TrieNode *NewNode = new TrieNode;

if (NewNode)
{
int i;

NewNode->isLeaf = false;

for (i = 0; i < ALPHABET_SIZE; i++)
NewNode->children[i] = NULL;
}

return NewNode;
}void insert(struct TrieNode *root, string key)
{
int length = key.length();
int index;

struct TrieNode *Node = root;

for (int level = 0; level < length; level++){
index = CHAR_TO_INDEX(key[level]);
if (!Node->children[index]){
Node->children[index] = getNode();
}
Node = Node->children[index];
}

// mark last node as leaf
Node->isLeaf = true;
}

int countChildren(struct TrieNode *node, int *index)
{
int count = 0;
for (int i=0; i<ALPHABET_SIZE; i++)
{
if (node->children[i] != NULL){
count++;
*index = i;
}
}
return (count);
}

bool isLeafNode(struct TrieNode* root){
return root->isLeaf != false;
}

void display(struct TrieNode* root, char str[], int level){
if (isLeafNode(root)){
str[level] = '\0';
cout << "--" << str << endl;
}

int i;
for (i = 0; i < ALPHABET_SIZE; i++){
if (root->children[i]){
str[level] = i + 'a';
display(root->children[i], str, level + 1);
}
}
}

void findCommon(struct TrieNode *root, char str[], int level){
struct TrieNode *pCrawl = root;
int index;
char character;

while (countChildren(pCrawl, &index) == 1 && pCrawl->isLeaf == false){
pCrawl = pCrawl->children[index];
character = char('a'+index);
cout << character;
}
cout << endl;
display(root, str, level);
}int main()
{
int level = 0;
char str[20];
struct TrieNode *root = getNode();
string arr[] = {"ozer", "oz", "ozmen"};
int n = sizeof (arr) / sizeof (arr[0]);
int i;
for(i=0; i<n; i++)
insert(root, arr[i]);

findCommon(root, str, level);
}

В findCommon Функция ищет общий префикс, но находит только один префикс. Например, если сейчас arr[] = {"ozer", "oz", "ozmen"} это печатает:

--oz
oz
ozer
ozmen

Но я хочу найти целые префиксы, например, arr[] = {"ozer", "oz", "ozmen", "table", "tabi"}, Я хотел бы напечатать как:

  --oz
oz
ozer
ozmen
--tab
tabi
table

Можете ли вы дать мне представление о том, как получить этот вывод?

-1

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]