poj 3630 Phone List(字典树)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接: http://poj.org/problem?id=3630

思路分析:

求在字符串中是否存在某个字符串为另一字符串的前缀:

即对于某个字符串而言，其是否为某个字符串的前缀,或存在某个其先前的字符串为其前缀；

(1)若该字符串为某个字符串前缀，则存在一条从根节点到该字符串的最后一个字符串的路径;

(2)若存在某个字符串为该字符串前缀，则在该字符串的查找路径中存在一条子路径，路径的最后的结点的endOfWord

标记为true，表示存在某个字符串为其前缀；

代码：

#include <iostream>
using namespace std;const int MAX_N = ;
struct Trie
{
bool endOfWord;
Trie *next[MAX_N];
Trie()
{
for (int i = ; i < MAX_N; ++i)
next[i] = NULL;
endOfWord = false;
}
};
int nodeCount = ;
Trie *root = NULL;
Trie memory[];bool insertAndJudge(char *word)
{
Trie *cur = root, *next;
int len = strlen(word); for (int i = ; i < len; ++ i)
{
int k = word[i] - ''; if (cur->next[k] == NULL)
{
next = &memory[nodeCount++];
cur->next[k] = next;
cur = cur->next[k];
}
else
if (i == len - || cur->next[k]->endOfWord == true)
return false;
else
cur = cur->next[k];
}
cur->endOfWord = true;
return true;
}int main()
{
int t; cin >> t;
while (t--)
{
int n;
bool flag = true;
char word[]; nodeCount = ;
memset(memory, , sizeof(memory));
root = &memory[nodeCount++]; cin >> n;
while (n--)
{
scanf("%s", word);
if (flag) flag = insertAndJudge(word);
}
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
} return ;
}