从一组字符串中查找所有以某个字符串开头的字符串

1、问题描述
你的任务是设计一种数据结构以及相应的算法，给定一个字符串A，利用该数据结构，从给定的一组字符串中找出以字符串A开头的所有字符串。

2、输入
输入的第一个参数是一个字符串A，A的长度是N，1≤N≤5000。
输入的第二个参数是一个整数M，表示给定的一组字符串中字符串的数目，1≤N≤5000。
输入的第三个参数是一组字符串，每个字符串的长度从1到5000不等。

3、输出
输出的第一个参数是一个整数K，表示匹配的字符串的数目。
输出的第二个参数是一组匹配的字符串。

4、输入输出样例
输入：”abc”, 5, “aaa”, “abc”, “abcd”, “abcdefg”, “acd”
输出：3, “abc”, “abcd”, “abcdefd”

我自己设计了一个数据结构，但是效率不是很高，请教各位大虾，有没有更好的方法？
#pragma warning(push, 3)
#include<map>
#include<vector>
using namespace std;
#pragma warning(pop)

template<class T>
class CTree
{
typedef map<short, void *> ContainerType;
typedef vector<T *> NodeArray;
public:
CTree()
{
}
virtual ~CTree()
{
Clear();
}
void Clear()
{
unsigned int nSize=0;
ContainerType::iterator it;
for(it=m_map.begin(); it!=m_map.end(); it++)
{
if((*it).first==0)
{
NodeArray * parr=(NodeArray *)(*it).second;
NodeArray & arr=*parr;
nSize=arr.size();
for(unsigned int i=0; i<nSize; i++)
{
T * pNode=arr[i];
delete pNode;
}
arr.clear();
delete parr;
}
else
{
CTree * pTree=(CTree *)(*it).second;
pTree->Clear();
delete pTree;
}
}
m_map.clear();
}
void AddNode(LPCTSTR lpszName, T * pT)
{
short nIndex=(short)*lpszName;
ContainerType::iterator it;
it=m_map.find(nIndex);
if(nIndex==0)
{
if(it==m_map.end())
{
NodeArray * parr=new NodeArray;
parr->push_back(pT);
m_map[0]=parr;
}
else
{
NodeArray * parr=(NodeArray *)(*it).second;
parr->push_back(pT);
}
}
else
{
LPTSTR szTemp=::CharNext(lpszName);
if(it==m_map.end())
{
CTree * pTree=new CTree;
pTree->AddNode(szTemp, pT);
m_map[nIndex]=pTree;
}
else
{
CTree * pTree=(CTree *)(*it).second;
pTree->AddNode(szTemp, pT);
}
}
}
void GetNodes(LPCTSTR lpszName, vector<T *> & vec)
{
short nIndex=*lpszName;
ContainerType::iterator it;
it=m_map.find(nIndex);
unsigned int nSize=0;
if(nIndex==0)
{
if(it!=m_map.end())
{
NodeArray & arr=*((NodeArray *)(*it).second);
nSize=arr.size();
for(unsigned int i=0; i< nSize; i++)
vec.push_back(arr[i]);
}
ContainerType::iterator it2;
for(it2=m_map.begin(); it2!=m_map.end(); it2++)
{
if((*it2).first==0)
continue;
CTree * pTree=(CTree *)(*it2).second;
pTree->CollectNode(vec);
}
}
else
{
if(it==m_map.end())
{
return;
}
else
{
LPTSTR szTemp=::CharNext(lpszName);
CTree * pTree=(CTree *)(*it).second;
pTree->GetNodes(szTemp, vec);
}
}
}
void CollectNode(vector<T *> & vec)
{
ContainerType::iterator it;
unsigned int nSize=0;
for(it=m_map.begin(); it!=m_map.end(); it++)
{
if((*it).first==0)
{
NodeArray & arr=*((NodeArray *)(*it).second);
nSize=arr.size();
for(unsigned int i=0; i< nSize; i++)
vec.push_back(arr[i]);
}
else
{
CTree * pTree=(CTree *)(*it).second;
pTree->CollectNode(vec);
}
}
}
protected:
// if TCHAR = 0 void * = vector<T *>
// else void * = CTree *
map<short, void *> m_map;
};

22 个解决方案

#1

#2

#3

用strcmp

#4

代码太长了，用stl的算法库可以很简洁地解决问题。我想大概是：

typedef list<string> slist;

class notprefix
{
public:
   bool operator ()(const string& str, const string& pref)
   {
      // stl里没有完全合适的函数，这样最快
      for(const char* s=str.c_str(), const char* p=pref.c_str();
          s++, p++;
          *s && *p)
      {
          if(*s != *p)
              return true;
      }
      return *p=='\0'? false:true;
   }
}

int main()
{
    slist strs;
    // 处理输入到strs
    slist::iterator iter = remove_if(strs.begin(), strs.end(), notperfix());
    strs.erase(iter, strs.end());
    cout << strs.length();
    for(iter=strs.begin(); iter<strs.end(); iter++)
        cout << " ,", << *iter;
}

That's all.

#5

这也是一个办法。但是如果查找要经常被调用的话，这个算法是不是有点慢？因为每次都要进行字符串比较

#6

这是个在VC6下编译过的版本，字符串比较是免不了的。这个算法应该是最快的，没有分配内存，没有使用临时对象。

#include <string>
#include <list>
#include <iostream>
#include <algorithm>

using namespace std;

typedef list<string> slist;

class notprefix
{
public:
notprefix(string pref):
_pref(pref)
{
}

bool operator ()(const string& str)
{
const char *s, *p;
for(s=str.c_str(), p=_pref.c_str(); *s && *p; s++, p++)
{
if(*s != *p)
return true;
}
return *p=='\0'? false:true;
}

private:
string _pref;
};

int main()
{
    slist strs;
string pref;
int nstr;
slist::iterator iter;

cout << "Input prefix: ";
cin >> pref;
cout << "Number of strings: ";
cin >> nstr;
strs.resize(nstr);
for(iter=strs.begin(); iter!=strs.end(); iter++)
{
cout << "Input string: ";
cin >> *iter;
}
    iter = remove_if(strs.begin(), strs.end(), notprefix(pref));
    strs.erase(iter, strs.end());
    cout << strs.size();
    for(iter=strs.begin(); iter!=strs.end(); iter++)
        cout << ", " << *iter;
return 0;
}

#7

我试一下

#8

用检索树，从树叶到树根的每条路径表示一个单词，路径经过的边表示字母。
这是效率最高的数据结构

#9

有一种称之为Trie树的数据结构，可以很快的解决这个问题，对了，就是楼上的“检索树”

#10

检索树！

#11

我自己给出的数据结构就是所谓的“检索树”
这种数据结构检索很快
但是生成树的效率不是很理想
2千多个节点就需要十几秒
不知各位有什么解决办法？

#12

#13

没试过，不过直接使用TStringList类效果怎么样？

#14

#15

TO:noho，你是怎么生成Trie的？怎么会这么慢？生成一棵Trie的复杂度应该是O(nlogn)呀。

#16

这个贴子有鬼，10-8发的，到今天才5天，人气有41690，也就是说，每天有8000多人的访问量，
这绝对不可能，就算1000个人有一个人回贴，也应该40多人回复

csdn应该是一个公平的地方，靠作弊获取人气，我真的看不起你

卑鄙，无耻

#17

同意：　ylm163net(文秀)　
无耻之极!!

#18

对，用stl的算法库可以很简洁地解决问题。

#19

我不知道我的算法是不是Trie Tree，我是这么做的
接收到一个字符串str，n=0，subtree = root(tree)，将str(n)插入到subtree，保证leftsibling小于等于str(n)，rightsibling大于str(n)，然后n++，subtree=上一次插入的node，重复插入。
大家可以看一下我的代码。
但是效率就是特别低。
另外，Trie Tree算法在哪儿能找到？

#20

#21

我以为构造类似DFA的算法效率比较高，其实和starfish(海星)的算法也比较类似

#22

小弟初到宝地，请各位同行多多指教

#1

#2

#3