鏈接:
http://poj.grids.cn/practice/2797/
這題乍看之下確實(shí)沒什么思路,后面終于明白題意了,然后突然想到可以用字典樹做,速度當(dāng)然會是非常快的...
但是其實(shí)還有一種更簡單的方法,那就是對所有字符串排序之后,每個(gè)字符串的前綴長度其實(shí)就是由其前一個(gè)和后一個(gè)字符串共同決定,
nLen = max(nOne, nTwo), nOne 和 nTwo就分別代表當(dāng)前字符串和前后字符串公告部分的長度+1后的值...
代碼寫出來寫非常簡單...同學(xué)這樣實(shí)現(xiàn)了下,也輕松過了...
然后我就辛苦的寫了一棵字典樹...可能我的寫法不是很標(biāo)準(zhǔn),因?yàn)槲覜]參考什么模板,自己硬想出來怎么寫的...
我的想法是開一個(gè)靜態(tài)大數(shù)組,第一個(gè)結(jié)點(diǎn)作為根,不存儲數(shù)據(jù),從第二個(gè)結(jié)點(diǎn)開始作為自由空間分配...
其實(shí),就是對26顆字典樹虛擬了個(gè)無數(shù)據(jù)的根結(jié)點(diǎn)...
使用了虛擬的根結(jié)點(diǎn)后,代碼比用26個(gè)根結(jié)點(diǎn)簡潔很多...
剛開始我就假設(shè)1-26號結(jié)點(diǎn)分別為a-z,作為26顆樹的根,
而且下26個(gè)結(jié)點(diǎn)的位置我用的是索引,沒用指針,后面換成了指針,代碼看起來更舒服了...
#include <stdio.h>
#include <string.h>
#define LETTER_NUM 26
#define WORD_LEN_MAX 25
#define WORD_NUM_MAX 1030
#define NODE_MAX (WORD_LEN_MAX * WORD_NUM_MAX + 10)
struct WORD_TREE
{
char ch;
WORD_TREE* next[LETTER_NUM];
int nTime;
};
WORD_TREE tree[NODE_MAX];
WORD_TREE* pFreeNode = tree + 1;//第一個(gè)結(jié)點(diǎn)作為頭結(jié)點(diǎn),不存儲數(shù)據(jù)
char szWords[WORD_NUM_MAX][WORD_LEN_MAX];
void AddToTree(char* pszStr)
{
WORD_TREE* pTree = tree;
while (*pszStr && pTree->next[*pszStr - 'a'])
{
pTree = pTree->next[*pszStr - 'a'];
pTree->nTime++;
++pszStr;
}
while (*pszStr)
{
pFreeNode->ch = *pszStr;
pFreeNode->nTime++;
pTree->next[*pszStr - 'a'] = pFreeNode;
pTree = pFreeNode;
++pszStr;
++pFreeNode;
}
}
int FindPrefix(char* pszStr)
{
WORD_TREE* pTree = tree;
int nLen = 0;
while (*pszStr)
{
++nLen;
pTree = pTree->next[*pszStr - 'a'];
if (pTree->nTime <= 1)
{
break;
}
++pszStr;
}
return nLen;
}
int main()
{
int nCount = 0;
while (scanf("%s", szWords[nCount]) != EOF)
{
AddToTree(szWords[nCount]);
nCount++;
}
for (int i = 0; i < nCount; ++i)
{
int nLen = FindPrefix(szWords[i]);
printf("%s ", szWords[i]);
for (int j = 0; j < nLen; ++j)
{
putchar(szWords[i][j]);
}
putchar('\n');
}
return 0;
}