HDOJ1251(前缀匹配---分块查找&map应用)

分块查找算法

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int SIZE=+;

const int BLOCKS=; //块的大小

char word[SIZE][];

char pre[];

int Num[];

bool isPre(char mo[],char so[])

{

    int i=,j=;

    while(mo[i]&&so[j])

    {

        if(mo[i]!=so[j])

            return false;

        i++;

        j++;

    }

    if(so[j]=='\0')

        return true;

    return false;

}

int main()

{

    int cnt=;

    char fin[]={'\0'};

    while(gets(fin))

    {

        if(fin[]=='\0')

            break;

        int key=fin[]-'a';

        int pos=key*BLOCKS+Num[key];

        Num[key]++;

        strcpy(word[pos],fin);

    }

    while(scanf("%s",pre)!=EOF)

    {

        int num=;

        int key=(pre[]-'a');

        int start=key*BLOCKS;

        for(int i=start;i<start+Num[key];i++)

        {

            if(isPre(word[i],pre))

                num++;

        }

        printf("%d\n",num);

    }

    return ;

}

利用STL库中的map解决

#include<iostream>

#include<cstdio>

#include<string>

#include<map>

using namespace std;

map<string, int> word;

int main()

{

    string x="";

    while(true)

    {

        char a;

        scanf("%c",&a);

        if(a=='\n')

        {

            scanf("%c",&a);

            x="";

        }

        if(a=='\n')

            break;

        x+=a;

        word[x]++;

    }

    string pre;

    while(cin>>pre)

    {

        cout<<word[pre]<<endl;

    }

    //感受到STL的威力了么

    return ;

}