Dumb feature Gym - 102020D 【 字典树 】

D - Dumb feature

 Gym - 102020D  

&：字典树的模板题，根据来的串建树，再查询。不过当时没弄出来，要映射一下子，把字母映射成键盘上的数字。

ps：这题的数据应该是有问题，只统计小于100的，然后直接用 map 也可以水过，不过不建议。

//引自 lxw
#include <cstdio>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1000010;
const int SIZE = 15;

int ch[N][SIZE];
int val[N],sz;
int ans;

void init()  // 初始化
{
    sz = 1;
    memset(ch,0,sizeof(ch));
    memset(val,0,sizeof(val));
}
int getId(int x)
{
    if(x <= 3) return 2;
    if(x <= 6) return 3;
    if(x <= 9) return 4;
    if(x <= 12) return 5;
    if(x <= 15) return 6;
    if(x <= 19) return 7;
    if(x <= 22) return 8;
    if(x <= 26) return 9;
}
void creat(char *s)
{
    int u = 0, len = strlen(s);
    for(int i = 0; i < len; i ++)
    {
        int c = getId(s[i] - 'a' + 1);
        if(!ch[u][c]) ch[u][c] = sz++;
        u = ch[u][c];
        val[u] ++;
    }
}
int query(char *s)
{
    int u = 0, len = strlen(s);
    for(int i = 0; i < len; i ++)
    {
        int c = s[i] - '0';
        if(!ch[u][c]) return 0;
        u = ch[u][c];
    }
    return val[u];
}
char s[100005];
int main()
{
    int n,q;
    while(~scanf("%d %d", &n, &q))
    {
        init();
        for(int i = 0; i < n ; i ++)
        {
            getchar();
            scanf("%s", s);
            creat(s);
        }
        while(q--)
        {
            getchar();
            scanf("%s", s);
            printf("%d\n",query(s));
        }
    }
    return 0;
}

ps做法：

//引自 zm
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include<map>
using namespace std;
typedef long long ll;
map<string,int> mp;
char s[100005];
char a[100005];
int main()
{
    int n,m;
    scanf("%d %d",&n, &m);
    for(int j = 1;j <= n;j++)
    {
        scanf("%s",a);
        int len = strlen(a);
        for(int i = 0;i < min(len,100);i++)
        {
            if(a[i] == 'a'||a[i] == 'b'||a[i] == 'c') s[i] = '2';
            else if(a[i] == 'd'||a[i] == 'e'||a[i] == 'f') s[i] = '3';
            else if(a[i] == 'g'||a[i] == 'h'||a[i] == 'i') s[i] = '4';
            else if(a[i] == 'j'||a[i] == 'k'||a[i] == 'l') s[i] = '5';
            else if(a[i] == 'm'||a[i] == 'n'||a[i] == 'o') s[i] = '6';
            else if(a[i] == 'p'||a[i] == 'q'||a[i] == 'r'||a[i] == 's') s[i] = '7';
            else if(a[i] == 't'||a[i] == 'u'||a[i] == 'v') s[i] = '8';
            else if(a[i] == 'w'||a[i] == 'x'||a[i] == 'y'||a[i] == 'z') s[i] = '9';
            s[i+1] = '\0';
            mp[s]++;
        }
    }
    while(m--)
    {
        scanf("%s", a);
        a[100] = '\0';
        printf("%d\n",mp[a]);
    }
    return 0;
}