trie_suffix.cpp

后缀tire树（tire图）

// trie树，各个字符的长度之和为n。O(n)实现排序
#include <iostream>
#include <queue>
using namespace std;

const int maxn = 26;
const int maxu = 1000000;
const int maxl = 10001;
char pattern[maxl][maxl];
int size = 0;
struct trie
{
	trie *child[maxn], *father, *suffix;
	char data;
	bool isEdge[maxn];
	bool isWord;
	int ind;
}*root, use[maxu];
void init()
{
	memset(use, 0, sizeof(trie) * size);
	size = 0;
	root = &use[size++];
}
int insert(char* str, int ind)
{
	trie* p = root;
	while(*str)
	{
		int i = *str - 'a';
		if(p->child[i] == NULL)
		{
			p->child[i] = &use[size++];
			p->child[i]->father = p;
			p->child[i]->data = *str;
			p->isEdge[i] = true;
			p = p->child[i];
		}
		else
			p = p->child[i];
		str++;
	}
	if(p->isWord)	// 单词已经存在则返回-1
		return -1;
	p->isWord = true;
	p->ind = ind;
	return 0;
}

void DFS(trie* p, int k, char* str, int i)
{
	if(p == NULL)
		return ;
	str[i] = char(k + 'a');
	if(p->isWord)
	{
		str[i+1] = 0;
		printf("%s\n", str);
	}
	for(int j = 0; j < maxn; j++)
	{
		if (p->isEdge[j])
		{
			DFS(p->child[j], j, str, i + 1);
		}
	}
}

void build()
{
	int i;
	trie* p = root;
	p->suffix = root;
	queue<trie*> que;
	for (i = 0; i < maxn; i++)
	{
		if (p->child[i])
		{
			p->child[i]->suffix = root;
			que.push(p->child[i]);
		}
		else
			p->child[i] = root;
	}
	while(!que.empty())
	{
		p = que.front();
		que.pop();
		i = p->data - 'a';

		// calculate suffix node
		if (p->father == root)
		{
			p->suffix = root;
		}
		else
		{
			trie* s = p->father->suffix;
			while (s != root)
			{
				if (s->child[i])
				{
					p->suffix = s->child[i];
					break;
				}
				s = s->suffix;
			}
			if (s == root)
			{
				p->suffix = root->child[i];
			}
		}
		for (i = 0; i < maxn; i++)
		{
			if (p->child[i]) 
			{
				que.push(p->child[i]);
			}
			else
			{
				trie* s = p->suffix;
				while (s != root)
				{
					if (s->child[i])
					{
						p->child[i] = s->child[i];
						break;
					}
					s = s->suffix;
				}
				if (s == root)
				{
					p->child[i] = root->child[i];
				}
			}
		}
	}
}

int mutimatch(char* str)
{
	trie* p = root;
	while (p && *str)
	{
		int ind = *str - 'a';
		p = p->child[ind];
		if (p->isWord)
		{
			ind = p->ind;
			printf("match %s\n", pattern[ind]);
		}
		str++;
	}
}

int main()
{
	int i, j, n;
	char str[512];
	init();
	scanf("%d", &n);
	for(i = 0; i < n; i++)
	{
		scanf("%s", &pattern[i]);
		insert(pattern[i], i);
	}
	build();
	scanf("%s", str);
	mutimatch(str);
	for(i = 0; i < maxn; i++)
	{
		if (root->isEdge[i])
		{
			DFS(root->child[i], i, str, 0);			
		}
	}
	return 0;
}