统计难题

【题目类型】Trie

&题解：

Trie的模板题,只不过这题坑点在没给数据范围,改成5e5就可以过了,用的刘汝佳蓝书模板

&代码：

#include <cstdio>

#include <bitset>

#include <iostream>

#include <set>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

typedef long long ll;

const int maxNode= 500000 +7,sigmaSize=26;

struct Trie

{

    int ch[maxNode][sigmaSize],sz,val[maxNode];

    Trie(){sz=1; memset(ch[0],0,sizeof(ch[0])); memset(val,0,sizeof(val));}

    int idx(char c){return c-'a';}

    void insert(char* s)

    {

        int u=0,n=strlen(s);

        for(int i=0;i<n;i++){

            int c=idx(s[i]);

            if(!ch[u][c]){

                memset(ch[sz],0,sizeof(ch[sz]));

                ch[u][c]=sz++;

            }

            u=ch[u][c];

            val[u]++;

        }

    }

    int query(char* s)

    {

        int u=0,n=strlen(s);

        for(int i=0;i<n;i++){

            int c=idx(s[i]);

            if(!ch[u][c]){

                return 0;

            }

            u=ch[u][c];

        }

        return val[u];

    }

}tr;

char s[23];

int main()

{

    while(1){

        gets(s);

        int n=strlen(s);

        if(n==0) break;

        tr.insert(s);

    }

    while(gets(s)){

        printf("%d\n",tr.query(s));

    }

    return 0;

}

巴特西

HDU 1251 统计难题(Trie)

统计难题

最新文章

热门文章