POJ 3080 Blue Jeans Trie後綴樹解法

POJ 3080 Blue Jeans Trie後綴樹解法

題目是牛仔褲的意思，不過看不出題意和Blue Jeans有什麼關系。

本題的數據是很水的，數據量小，故此可以使用非常暴力的方法過，也可以使用不那麼暴力的KMP過。

這裡使用更加不暴力的Trie後綴樹過，這種解法就一點都不水了，呵呵。

思路：

1 建立所有字符串的後綴Trie樹

2 增加額外信息，看每過路徑是否是所有的字符串都經過了，如果是，那麼就是合法的字符串了，查找最長的這樣的字符串

3 優化一下：如果不是所有字符串的經過的路徑，那麼就可以直接返回，不往下搜索了

最後，我發現刪除Trie都是很耗時的，不釋放Trie那麼速度是快很多的，需要內存自然高很多。

#include 
#include 

const int MAX_N = 61;
const int ALP_LEN = 4;
const int SIGNIFICANT = 3;
char DNAStr[MAX_N];

inline int charToint(char a)
{
	switch (a)
	{
	case 'A':
		return 0;
	case 'T':
		return 1;
	case 'G':
		return 2;
	case 'C':
		return 3;
	}
	return -1;//unexpected input
}

inline char intTochar(int i)
{
	switch (i)
	{
	case 0:
		return 'A';
	case 1:
		return 'T';
	case 2:
		return 'G';
	case 3:
		return 'C';
	}
	return '?';//unexpected input
}

struct Node
{
	int n, tab;
	Node *alpha[ALP_LEN];
	Node():n(0), tab(-1)
	{
		for (int i = 0; i < ALP_LEN; i++)
		{
			alpha[i] = NULL;
		}
	}
};

void delTrie(Node *rt)
{
	if (rt)
	{
		for (int i = 0; i < ALP_LEN; i++)
		{
			if (rt->alpha[i]) delTrie(rt->alpha[i]);
			rt->alpha[i] = NULL;
		}
		delete rt;
	}
}

Node *Trie;
int tab;
void insert(char *chs, int len)
{
	Node *pCrawl = Trie;
	for (int i = 0; i < len; i++)
	{
		int k = charToint(chs[i]);
		if (!pCrawl->alpha[k]) pCrawl->alpha[k] = new Node;
		pCrawl = pCrawl->alpha[k];
		if (pCrawl->tab != tab)//防止重復計算
		{
			pCrawl->tab = tab;
			pCrawl->n++;
		}
	}
	if (pCrawl->tab != tab)
	{
		pCrawl->tab = tab;
		pCrawl->n++;
	}
}

int maxLen, pid, n;
char path[MAX_N], res[MAX_N];
void search(Node *rt)
{
	for (int i = 0; i < ALP_LEN; i++)
	{
		if (rt->alpha[i] && rt->alpha[i]->n == n)
		{
			path[pid++] = intTochar(i);
			if (maxLen < pid)
			{
				maxLen = pid;
				path[pid] = '\0';
				strncpy(res, path, pid+1);
			}
			search(rt->alpha[i]);
			pid--;
		}
	}
}

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		Trie = new Node;
		scanf("%d", &n);
		getchar(); // get rid of '\n'
		tab = 0;
		for (int i = 0; i < n; i++)
		{			
			gets(DNAStr);
			int len = MAX_N-1;
			tab++;
			for (char *p = &DNAStr[0]; *p; p++)
			{
				insert(p, len);
				len--;
			}
		}
		maxLen = 0, pid = 0;
		search(Trie);

		if (maxLen < SIGNIFICANT)
		{
			puts("no significant commonalities");
		}
		else
		{
			printf("%s\n", res);
		}

		//delTrie(Trie);
	}
	return 0;
}