统计难题 HDU1251

简单方法：

#include<bits/stdc++.h>

using namespace std;

int main()

{

 char s[];

 map<string,int>ma;

 while(gets(s)&&strlen(s)!=)

 {

     for(int i=strlen(s)-;i>=;i--)

     {

         ma[s]++;

         s[i]='\0';

  //  cout<<s<<endl;

     }

 }

 while(gets(s))

 {

     printf("%d\n",ma[s]);

 }

}

但是当数据过多的时候map就不行了

要用新的数据结构——字典树

有两种实现的方法一种是指针一种是数组

数组的实现方法更为方便高明快速

注意数组一定要开到一百万不然wa ！！！

#include<bits/stdc++.h>

using namespace std;

int trie[][]={};

int sum[]={};

int pos=;

void insert1( char *word )

{

    int root=;

    for(int i=;i<strlen(word);i++)

    {   int ch=word[i]-'a';

        if(trie[root][ ch ]==)

            trie[root][ ch ]=++pos;

        root=trie[root][ch];

        sum[root]++;

    }

}

int find1(char *word)

{

    int root=;

    for(int i=;i<strlen(word);i++)

    {

        int ch=word[i]-'a';

        if(trie[root][ ch ]==)return ;

        root=trie[root][ch];

    }

    return sum[root];

}

int main()

{

    char word[];

    while(gets(word))

    {

        if(strlen(word)==)break;

        insert1(word);

    }

    while(gets(word))

    {

        printf("%d\n",find1(word));

    }

}

巴特西

统计难题 HDU1251

最新文章

热门文章