本文主要是介绍trie基本用法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
poj2001 poj2503 poj3630poj1056poj1451
1.单词查找树
我们需要将一个确定的单词列表建出一棵单词查找树，满足
1. 根结点不包含字母，除根结点外的每个都仅含一个大写英文
字母；
2. 从根结点到某一结点，路径上经过的字母依次连起来所构成
的字母序列，称为该结点对应的单词。单词列表中的每个词，都是
该单词查找树某个结点所对应的单词；
3. 在满足上述条件下，该单词查找树的结点数最少。
统计出该单词查找树的结点数目。
输入格式
若干行单词，描述单词列表。
输出格式
一个数字，表示结点数目。
样例输入
A
AN
ASP
AS
ASC
ASCII
BASIC
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
using namespace std;
char ch[100];
struct Node
{
int next[26];
}temp[100000];
int num;
void build(char *s)
{
int len = strlen(s);
int p = 0;
for (int i = 0; i < len; i++)
{
int t = s[i] - 'A';
if (!temp[p].next[t])
{
temp[p].next[t] = ++num;
}
p = temp[p].next[t];
}
}
void input()
{
int n;
while (cin >> n, n)
{
num = 0;
memset(temp, 0, sizeof(temp));
for (int i = 0; i < n; i++)
{
scanf("%s", ch);
build(ch);
}
cout << num + 1 << endl;
}
}
int main()
{
input();
return 0;
}
2.问所给单词中是否有的单词有公共前缀 hdu1671
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
using namespace std;
int n;
char ch[10000 + 1][20];
struct Node
{
int next[10];
int num;
}temp[100000 + 1];
bool ok;
int num;
void build(char *s)
{
int len = strlen(s), p = 0;
for (int i = 0; i < len; i++)
{
int t = s[i] - '0';
if (!temp[p].next[t])
{
temp[p].next[t] = ++num;
}
p = temp[p].next[t];
temp[p].num++;
}
}
void dfs(char *s)
{
int len = strlen(s), p = 0;
for (int i = 0; i < len; i++)
{
int t = s[i] - '0';
if (temp[p].next[t])
{
p = temp[p].next[t];
}
}
if (temp[p].num > 1)
{
ok = false;
}
}
void input()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
num = 0;
memset(temp, 0, sizeof(temp));
for (int i = 0; i < n; i++)
{
scanf("%s", ch[i]);
build(ch[i]);
}
ok = true;
for (int i = 0; i < n; i++)
{
if (ok) dfs(ch[i]);
}
printf("%s\n", ok ? "YES" : "NO");
}
}
int main()
{
input();
return 0;
}
3.判断一个单词是否在单词表中,不在输出并加入单词表
#include <iostream>
#include <string.h>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct Node
{
int next[26];
int arrive;
}temp[100000];
char ch[100];
int num;
void build(char *s)
{
int len = strlen(s), p = 0;
for (int i = 0; i < len; i++)
{
int t = s[i] - 'a';
if (!temp[p].next[t])
{
temp[p].next[t] = ++num;
}
p = temp[p].next[t];
}
temp[p].arrive = 1;
}
bool dfs(char *s)
{
int len = strlen(s), p = 0;
for (int i = 0; i < len; i++)
{
int t = s[i] - 'a';
if (temp[p].next[t])
{
p = temp[p].next[t];
}
else
{
return false;
}
}
if (temp[p].arrive)
{
return true;
}
else
{
return false;
}
}
void input()
{
int n;
cin >> n;
num = 0;
memset(temp, 0, sizeof(temp));
for (int i = 0; i < n; i++)
{
scanf("%s", ch);
build(ch);
}
while (true)
{
scanf("%s", ch);
if (!dfs(ch))
{
cout << ch << endl;
build(ch);
}
}
}
int main()
{
input();
return 0;
}
4.单词排序后输出
#include <iostream>
#include <string.h>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct Node
{
int next[26];
int arrive;
}temp[100000];
char ch[100];
int num;
void build(char *s)
{
int len = strlen(s), p = 0;
for (int i = 0; i < len; i++)
{
int t = s[i] - 'a';
if (!temp[p].next[t])
{
temp[p].next[t] = ++num;
}
p = temp[p].next[t];
}
temp[p].arrive++;
}
void dfs(int p, char s[], int len)
{
while (temp[p].arrive--)
{
cout << s << endl;
}
for (int i = 0; i < 26; i++)
{
if (temp[p].next[i])
{
s[len++] = i + 'a';
dfs(temp[p].next[i], s, len);
len--;
}
}
}
char chs[1000];
void input()
{
int n;
cin >> n;
num = 0;
memset(temp, 0, sizeof(temp));
for (int i = 0; i < n; i++)
{
scanf("%s", ch);
build(ch);
}
dfs(0, chs, 0);
}
int main()
{
input();
return 0;
}
5文章解密
给出有 N 个单词的字典，和一篇长 L 的没有标点符号的文章。问这文章
有多少种解释方式。
输入格式
第一行，一个数字 N；
接下来 N 行，每行一个单词，描述字典内容；
接下来若干字符，描述文章。
输出格式
一个数字，表示所求答案并对 12345679 取模。
样例输入
5
ab
cb
bc
ba
a
abcba
样例输出
2
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
using namespace std;
struct Node
{
int next[26];
int arrive;
}temp[100000];
char ch[100];
int num;
void build(char *s)
{
int len = strlen(s), p = 0;
for (int i = 0; i < len; i++)
{
int t = s[i] - 'a';
if (!temp[p].next[t])
{
temp[p].next[t] = ++num;
}
p = temp[p].next[t];
}
temp[p].arrive = 1;
}
bool dfs(string &s)
{
int len = s.length(), p = 0;
for (int i = 0; i < len; i++)
{
int t = s[i] - 'a';
if (temp[p].next[t])
{
p = temp[p].next[t];
}
else
{
return false;
}
}
if (temp[p].arrive)
{
return true;
}
else
{
return false;
}
}
int f[1000];
void input()
{
int n;
cin >> n;
memset(temp, 0, sizeof(temp));
memset(f, 0, sizeof(f));
for (int i = 0; i < n; i++)
{
scanf("%s", ch);
build(ch);
}
scanf("%s", ch);
int len = strlen(ch);
f[0] = 1;
for (int i = 0; i < len; i++)
{
for (int j = i; j < len; j++)
{
string s = "";
for (int k = i; k <= j; k++)
{
s += ch[k];
}
if (dfs(s))
{
f[i + s.length()] += f[i];
}
}
}
for (int i = 0; i <= len; i++)
{
cout << f[i] << ' ';
}
cout << endl;
cout << f[len] << endl;
}
int main()
{
input();
return 0;
}
al3942
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string.h>
using namespace std;
int temp[400000 + 5][26];
int val[400000 + 5];
char ch[100 + 5];
int num;
int f[300000 + 5];
char h[300000 + 5];
int l;
void build(char *s)
{
int len = strlen(s), p = 0;
for (int i = 0; i < len; i++)
{
int t = s[i] - 'a';
if (!temp[p][t])
{
memset(temp[num], 0, sizeof(temp[num]));
val[num] = 0;
temp[p][t] = num++;
}
p = temp[p][t];
}
val[p] = len;
}
void dfs(int k)
{
int p = 0;
for (int i = k; i < l; i++)
{
int t = h[i] - 'a';
if (!temp[p][t])
{
break;
}
p = temp[p][t];
if (val[p])
{
f[k] = (f[k + val[p]] + f[k]) % 20071027;
}
}
}
void input()
{
int cases = 0;
while (scanf("%s", h) != EOF)
{
int n;
scanf("%d", &n);
memset(f, 0, sizeof(f));
memset(temp[0], 0, sizeof(temp[0]));
num = 1;
for (int i = 0; i < n; i++)
{
scanf("%s", ch);
build(ch);
}
l = strlen(h);
f[l] = 1;
for (int i = l - 1; i >= 0; i--)
{
dfs(i);
}
printf("Case %d: %d\n", ++cases, f[0]);
}
}
int main()
{
input();
return 0;
}
这篇关于trie基本用法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
