【zzuliOJ】1901 - 985的SS串难题（字典树 & dfs）

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define idx(x) (x-'a')
int dic[8]={1,4,9,16,25,2,8,18};
struct Trie
{
	Trie *next[26];
	int v;
	void clear()
	{
		v = 0;
		for (int i = 0 ; i < 26 ; i++)
			next[i] = NULL;
	}
}tree[1000000];
int ant;
string ans;
bool check(int x)
{
	for (int i = 0 ; i < 8 ; i++)
		if (x == dic[i])
			return true;
	return false;
}
void insert(char *s)
{
	int l = strlen(s);
	Trie *p = &tree[0] , *q;
	int used[26];
	CLR(used,false);
	for (int i = 0 ; i < l ; i++)
	{
		int id = idx(s[i]);
		if (p->next[id] == NULL)
		{
			q = &tree[ant++];
			q->v = p->v;
			p->next[id] = q;
			if (!used[id])
				q->v++;
		}
		used[id] = true;		//应该在这里标记，如果在上面会漏掉某些串 
		p = p->next[id];
	}
}
void bfs(Trie *root)
{
	for (int i = 0 ; i < 26 ; i++)
	{
		if (root->next[i] != NULL)
		{
			ans += ('a' + i);
			if (check(root->next[i]->v))
//				cout << ans << endl;
				printf ("%s\n",ans.c_str());
			bfs(root->next[i]);
//			ans.erase(ans.end()-1);
			ans = ans.substr(0,ans.length()-1);
		}
	}
}
void del(int n)
{
	for (int i = 1 ; i < n ; i++)
		tree[i].clear();
}
int main()
{
	int u;
	char s[1011];
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%s",s);
		ant = 1;
		tree[0].clear();
		int l = strlen(s);
		char t[1011];
		for (int i = 0 ; i < l ; i++)
		{
			strcpy(t,s+i);
			insert(t);
		}
		ans = "";
		bfs(&tree[0]);
		del(ant);
	}
	return 0;
}