題意：給定一個(gè)字典，要你判斷其中的任意兩個(gè)單詞是否可以組成另一個(gè)單詞。
解法：trie樹，記錄所有的單詞，然后再對(duì)每個(gè)檔次枚舉分隔點(diǎn)。神奇的是我釋放內(nèi)存就RE，不釋放就A了。沒搞懂。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 50005
#define KIND 26
struct TreeNode
{
int count;
TreeNode *next[KIND];
TreeNode()
{
count = 0;
memset(next, 0, sizeof(next));
}
}*root;
char data[N][105], data1[105], data2[105];
void Insert(char *s)
{
TreeNode *r = root;
for(; *s; s++)
{
int t = (*s) - 'a';
if(NULL == r->next[t])
{
r->next[t] = new TreeNode();
}
r = r->next[t];
}
r->count = 1;
}
bool Find(char *s)
{
int count = 0;
TreeNode *r = root;
for(; *s; s++)
{
int t = (*s) - 'a';
if(r->next[t] == NULL) return false;
r = r->next[t];
}
if(r->count) return true;
return false;
}
void Release(TreeNode *p)
{
for(int i = 0; i < KIND; i++)
{
if(p->next[i]) Release(p);
}
delete p;
}
int main()
{
int n = 0;
root = new TreeNode();
while(scanf("%s", data[n]) != EOF)
{
Insert(data[n]);
n++;
}
for(int i = 0; i < n; i++)
{
int l = strlen(data[i]);
for(int j = 1; j < l; j++)
{
int k;
for(k = 0; k < j; k++)
data1[k] = data[i][k];
data1[k] = '\0';
for(k = j; k < l; k++)
data2[k - j] = data[i][k];
data2[k - j] = '\0';
// strncpy(data1, data[i], j);
// strncpy(data2, data[i] + j, l - j + 1);
// puts(data1);puts(data2);
if(Find(data1) && Find(data2))
{
puts(data[i]);
break;
}
}
}
//Release(root);
return 0;
}