如果给定n个字符串,要你在其中寻找字符串s
思路:
- 暴力算法:挨个比较,直到找出O(nm)
- 如何让他的复杂度变回线性呢,就要用到Trie树了
- 建立一个树,每个节点对应一个编号,表示一个字母,如果要在这个节点下再加入一个字母,则节点编号数++——用ch[i][a]表示一条边,i是父亲节点的编号,a是一个字母,如果父亲对这个字母有连边,ch[i][a] = sz(编号)++,所以ch[i][a]对应字母a的编号,继续插入时从sz继续讨论
- 当一个字符串插入完成后,在这个字符串的最后字母上加上附加值,表示这个字母是一个字符串的终点,当附加值==0时,表示他不是任何字符串的终点,这个附加值可以是字符串的标号
建成的树如图(出自刘汝佳《算法竞赛入门经典训练指南》)
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 2000 + 10;
int d[MAXN];
//字母表为全体小写字母的Trie
struct Trie
{
int sz;
int ch[MAXN][26];
void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); sz = 1;} // 初始时只有一个根结点
int val[MAXN];
int cal(char a) { return a - 'a';}
// 插入字符串s,附加信息为v。注意v必须非0,因为0代表“本结点不是单词结点”
void insert(const char *s, int v)
{
int u = 0;
int n = strlen(s);
for(int i = 0; i < n; i++)
{
int c = cal(s[i]);
if(!ch[u][c]) // 结点不存在
{
memset(ch[sz], 0, sizeof(ch[sz])); //相当于申请新的内存空间(把即将加入的节点编号初始化)
val[sz] = 0; // 中间结点的附加信息为0
ch[u][c] = sz++; // 新建结点
}
u = ch[u][c]; // 往下走
}
val[u] = v; // 字符串的最后一个字符的附加信息为v
}
//找出字符串s并返回它的附加信息
int find(const char *s) //查找
{
int u = 0;
int n = strlen(s);
for(int i = 0; i < n; i++)
{
int c = cal(s[i]);
if(ch[u][c]) u = ch[u][c]; //如果下一个字符在树中,往下走
else return 0;
}
if(!val[u]) return 0; //如果最后一个字符没有附加信息,则没有该字符串
else return val[u];
}
};
Trie trie;
char str[MAXN];
int main()
{
trie.clear();
while(scanf("%s", str) == 1)
{
trie.insert(str, 3);
cout << trie.find(str) << endl;
}
return 0;
}