返回一个单词的前缀

1,前缀:就是能够代表这个单词的前n个字符,n最小.
如:abc  acc  前缀: ab  ac

语法的悲剧,让我整整浪费了一个上午,郁闷了一个下午.
问题终于还是找到了.

基于string的实现:

#include <iostream>
#include <fstream>
#include <vector>
#include <string>

using namespace std ;

class trie
{
private :
    int sum;
    trie* next[26];
public :
    trie():sum(0)
    {
        for(int i=0;i<26;i++)
            next[i]=NULL;
    }

    ~trie ()
    {
        int i ;
        for ( i = 0 ; i < 26 ; i++ )
        {
            delete next[i] ;
        }
    }
    void insert(string& str)
    {
        trie* tmp=this;
        for(int i=0;i<str.size();i++)
        {
            str[i]|=0x20;

            if(tmp->next[str[i]-'a']==NULL)
                tmp->next[str[i]-'a']=new trie;
            else
                tmp->next[str[i]-'a']->sum++;
            tmp=tmp->next[str[i]-'a'];
        }
    }

    int quary ( string& str )
    {
        trie* tmp=this;
        int n=0;
        for(int i=0;i<str.size();i++)
        {
            str[i]|=0x20;
            tmp=tmp->next[str[i]-'a'];
            n++;
            if(tmp==NULL)
                return n;
            if(tmp->sum==0)
                break;
        }
        return n;
    }
};

int main ()
{
    ifstream in("main.txt");
    string word;
    vector<string> vecstr;

    trie tree;
    while(getline(in,word))
    {
        vecstr.push_back(word);
        tree.insert(word);
    }


    int cnt;
    string pre;
    vector<string> vecpre;
    for(int i=0;i<vecstr.size();i++)
    {
        cnt=tree.quary(vecstr[i]);
        pre=vecstr[i].substr(0,cnt);
        vecpre.push_back(pre);
    }

    for(int i=0;i<vecstr.size();i++)
        cout<<vecstr[i]<<" "<<vecpre[i]<<endl;
	return 0 ;
}

基于const char*的实现:

#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std ;

class trie
{
public:
    trie() : sum(0)
    {
        int i;
        for (i = 0; i < 26; i++)
            child[i] = NULL;
    }
    ~trie()
    {
        int i;
        for (i = 0; i < 26; i++)
            delete child[i];
    }

    void insert(const char* key)
    {

        if (*key == '\0')
            return;
        assert((*key >= 'a' ) && (*key <= 'z'));
        int index = *key - 'a';
        if (child[index] == NULL)
            child[index] = new trie;
        else
            child[index] -> sum++;
        child[index] -> insert(key + 1);
    }

    int query(const char* key)
    {

        if (*key == '\0')
            return 0;
        assert((*key >= 'a' ) && (*key <= 'z'));
        int index = *key - 'a';
        if (child[index] == NULL)
            return 0;
        if ((child[index] -> sum) == 0)
            return 1;
        return 1 + child[index] -> query(key + 1);
    }
private:
    int sum;
    trie* child[26];
};
int main ()
{
    ifstream in("1.1.in");
    string word;
    vector<string> vecstr;
    trie t;
    while(getline(in, word))
    {
        //注意全部转化为小写
        for (int i = 0; i < (int)word.size(); i++)
            word[i] |= 0x20;
        //重复的只插入一次
        if (find(vecstr.begin(), vecstr.end(), word) == vecstr.end())
        {
            vecstr.push_back(word);
            t.insert(word.c_str());
        }
    }

    int cnt;
    string pre;
    vector<string> vecpre;
    for(int i = 0; i < static_cast<int>(vecstr.size()); i++)
    {
        cnt = t.query(vecstr[i].c_str());
        pre = vecstr[i].substr(0,cnt);
        vecpre.push_back(pre);
    }
    for(int i = 0; i < static_cast<int>(vecstr.size()); i++)
        cout<<vecstr[i]<<" "<<vecpre[i]<<endl;
	return 0 ;
}

评论

1 楼 bhjackson 2010-05-04  

能说说思路么？看不太懂。。。。