Я хочу найти самый длинный общий префикс в три. Вот мой код:
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
Можете ли вы дать мне представление о том, как получить этот вывод?
Задача ещё не решена.
Других решений пока нет …