中国英利 是干啥的？# PhotoGear - 摄影器材
w*x
1 楼
struct NODE
{
vector vecGUID;
NODE* nodes[256];
NODE() { memset(nodes, 0, sizeof(nodes)); }
};
void _inner_get_guid(NODE* pNode, const char* str, int k, vector& vec)
{
if (NULL == pNode)
return;
if (k <= 0)
{
vec = pNode->vecGUID;
return;
}
_inner_get_guid(pNode->nodes[*str], str+1, k-1, vec);
}
vector getGUID(const char* str, NODE* pRoot, int k)
{
vector vecRet;
if (NULL == pRoot || NULL == str || *str == 0 || k <= 0)
return vecRet;
_inner_get_guid(pRoot, str, k, vecRet);
return vecRet;
}
int GetTimes(const char* str, NODE* pRoot, int k)
{
if (NULL == pRoot || NULL == str || k <=0)
return -1;
int nLen = strlen(str);
if (nLen < k) return 0;
hash_map mp;
int nRet = 0;
for (int i = 0; i < nLen-k+1; i++)
{
vector vec = getGUID(str + i, pRoot, k);
for (vector::iterator it = vec.begin(); it != vec.end(); it++)
{
if (mp.find(*it) == mp.end())
mp[*it] = 1;
else mp[*it]++;
nRet = max(nRet, mp[*it]);
}
}
return nRet;
}
void _inner_insert_trie(NODE* pNode, const char* p, int guid)
{
if (NULL == p || pNode == NULL ||*p == 0)
return;
if (pNode->nodes[*p] == NULL)
pNode->nodes[*p] = new NODE();
pNode->nodes[*p]->vecGUID.push_back(guid);
_inner_insert_trie(pNode->nodes[*p], p+1, guid); //p+1 not p++
}
NODE* BuildTrie(const char* strs[], int guids[], int n)
{
if (strs == NULL || n <= 0)
return NULL;
NODE* pRoot = new NODE();
for (int i = 0; i < n; i++)
{
const char* p = strs[i];
while (*p != 0)
_inner_insert_trie(pRoot, p++, guids[i]);
}
return pRoot;
}
void test()
{
const char* strs[] = {
"abcdeacdefjgs",
"fabcesdef",
"13fsdfas",
"dageqwe",
"sadgwerq",
"asfgeqwr",
};
int guids[] = {0, 1, 2, 3, 4, 5};
NODE* pRoot = BuildTrie(strs, guids, 6);
int x = GetTimes("abcdef", pRoot, 3);
}
刚才手写花了大概25分钟, 两个小bug, 当场是预处理有一半没写完（现场大概提供30
分钟）.
bug free是不追求了, 预处理没写完实在不因该, 想想自己居然从来没动手写过一个
trie...
忽然想起当年二爷在西雅图说的现场build trie树是基本要求， 当时想想没当回事，
果然关键时刻挂球了， 对二爷的敬仰又深了一层啊...
{
vector
NODE* nodes[256];
NODE() { memset(nodes, 0, sizeof(nodes)); }
};
void _inner_get_guid(NODE* pNode, const char* str, int k, vector
{
if (NULL == pNode)
return;
if (k <= 0)
{
vec = pNode->vecGUID;
return;
}
_inner_get_guid(pNode->nodes[*str], str+1, k-1, vec);
}
vector
{
vector
if (NULL == pRoot || NULL == str || *str == 0 || k <= 0)
return vecRet;
_inner_get_guid(pRoot, str, k, vecRet);
return vecRet;
}
int GetTimes(const char* str, NODE* pRoot, int k)
{
if (NULL == pRoot || NULL == str || k <=0)
return -1;
int nLen = strlen(str);
if (nLen < k) return 0;
hash_map
int nRet = 0;
for (int i = 0; i < nLen-k+1; i++)
{
vector
for (vector
{
if (mp.find(*it) == mp.end())
mp[*it] = 1;
else mp[*it]++;
nRet = max(nRet, mp[*it]);
}
}
return nRet;
}
void _inner_insert_trie(NODE* pNode, const char* p, int guid)
{
if (NULL == p || pNode == NULL ||*p == 0)
return;
if (pNode->nodes[*p] == NULL)
pNode->nodes[*p] = new NODE();
pNode->nodes[*p]->vecGUID.push_back(guid);
_inner_insert_trie(pNode->nodes[*p], p+1, guid); //p+1 not p++
}
NODE* BuildTrie(const char* strs[], int guids[], int n)
{
if (strs == NULL || n <= 0)
return NULL;
NODE* pRoot = new NODE();
for (int i = 0; i < n; i++)
{
const char* p = strs[i];
while (*p != 0)
_inner_insert_trie(pRoot, p++, guids[i]);
}
return pRoot;
}
void test()
{
const char* strs[] = {
"abcdeacdefjgs",
"fabcesdef",
"13fsdfas",
"dageqwe",
"sadgwerq",
"asfgeqwr",
};
int guids[] = {0, 1, 2, 3, 4, 5};
NODE* pRoot = BuildTrie(strs, guids, 6);
int x = GetTimes("abcdef", pRoot, 3);
}
刚才手写花了大概25分钟, 两个小bug, 当场是预处理有一半没写完（现场大概提供30
分钟）.
bug free是不追求了, 预处理没写完实在不因该, 想想自己居然从来没动手写过一个
trie...
忽然想起当年二爷在西雅图说的现场build trie树是基本要求， 当时想想没当回事，
果然关键时刻挂球了， 对二爷的敬仰又深了一层啊...
