鏈接:
http://poj.grids.cn/practice/2797/
這題乍看之下確實沒什么思路,后面終于明白題意了,然后突然想到可以用字典樹做,速度當然會是非常快的...
但是其實還有一種更簡單的方法,那就是對所有字符串排序之后,每個字符串的前綴長度其實就是由其前一個和后一個字符串共同決定,
nLen = max(nOne, nTwo), nOne 和 nTwo就分別代表當前字符串和前后字符串公告部分的長度+1后的值...
代碼寫出來寫非常簡單...同學這樣實現了下,也輕松過了...
然后我就辛苦的寫了一棵字典樹...可能我的寫法不是很標準,因為我沒參考什么模板,自己硬想出來怎么寫的...
我的想法是開一個靜態大數組,第一個結點作為根,不存儲數據,從第二個結點開始作為自由空間分配...
其實,就是對26顆字典樹虛擬了個無數據的根結點...
使用了虛擬的根結點后,代碼比用26個根結點簡潔很多...
剛開始我就假設1-26號結點分別為a-z,作為26顆樹的根,
而且下26個結點的位置我用的是索引,沒用指針,后面換成了指針,代碼看起來更舒服了...
#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;//第一個結點作為頭結點,不存儲數據
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;
}