P4407 [JSOI2009] 电子字典 题解

标签：Hash 题解 ll 枚举 一位 插入 电子字典 P4407 字母

题目：P4407

这题差不多就是 P1688 的改版。

参考一下我在 P1688 的做法，我们继续使用 Hash，然后只要考虑如何去重就好了。

于是就有了这个暴力的想法：# 代表修改，@ 代表添加，$ 代表删除。

接下来我们来暴力去重。

考虑怎么样会使单词被重复统计。

1. 在两个相邻且相同的字母中选一个删掉
2. 在一个字母旁添加一个一模一样的字母
3. 修改的字符不会被重复统计

然后我们就可以愉快去重了。

对于上面的 1、2 两种情况，考虑只统计连续相同字母中的最后一个字母。

具体操作：

1. 删除
   (1). 插入字典时： 一位一位枚举，遇到连续相同字母时只改最后一位并塞入 Hash。
   (2). 查询时： 所有空位全部插入 $ 并在 Hash 中查询。

2. 添加
   (1). 插入字典时： 所有空位全部插入 @ 并塞入 Hash 中。
   (2). 查询时： 一位一位枚举，遇到连续相同字母时只改最后一位并在 Hash 中查询。

3. 修改
   照常枚举。

为什么要这样分类操作？

我们会发现只有在 1(1) 和 2(2) 情况下我们才能确切地知道当前字符串中枚举到的是不是重复字母，而另外两种情况是我们插入的，可以代表任意字符，只插一位会漏掉很多不同字母的情况。

这样操作就可以把重复的筛掉，且不会过多地去掉合法情况，暴力且能 A。

Naive Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll Min(ll x, ll y){return x < y ? x : y;}
inline ll Max(ll x, ll y){return x > y ? x : y;}
inline ll rd(){
	ll x = 0;bool f = true;char c = getchar();
	while (c < '0' || c > '9'){if (c == '-') f = false; c = getchar();}
	while (c >= '0' && c <= '9'){x = (x<<3) + (x<<1) + (c ^ 48);c = getchar();}
    return f ? x : -x;
}
inline string srd(){
    char c = getchar();string res = "";
    while (c < 'a' || c > 'z')c = getchar();
    while(c >= 'a' && c <= 'z')res += c, c = getchar();
    return res;
}
const int N = 1e4 + 10, M = 1e6 + 7;

class Hash_table{
    private: 

    struct Node{
        int nextt, num;// num就是该状态下的单词个数
        string str;
    }data[N * 60];int head[M + 10], cnt;

    int h(string s){
        int l = s.size();
        int res = 0;
        for(int i = 0; i < l; ++i)
            res = ((res << 3) + (s[i] - 'a') + M) % M;
        return res;
    }

    public: 

    int find(string s){
        int key = h(s);
        for(int i = head[key]; i; i = data[i].nextt)
            if(s == data[i].str)
                return data[i].num;
        return 0;
    }

    void insert(string s){
        int key = h(s);
        for(int i = head[key]; i; i = data[i].nextt){
            if(s == data[i].str){
                data[i].num++;
                return ;
            }
        }
        data[++cnt].nextt = head[key];
        data[cnt].num = 1;
        data[cnt].str = s;
        head[key] = cnt;
        return ;
    }
}H;

int n, m;
string s, tmp, tmp1, tmp2;

int main(){
    n = rd(), m = rd();
    for(int i = 1; i <= n; ++i){
        s = srd();H.insert(s);
        int l = s.size();
        tmp = s;
        for(int j = 0; j < l; ++j){
            tmp[j] = '#';
            H.insert(tmp);
            if(j == l - 1 || s[j] != s[j + 1]){// 只删除最后一个
                tmp[j] = '#';
                H.insert(tmp);
            }
            tmp[j] = s[j];
        }

        if(l < 20){
            for(int j = 0; j <= l; ++j){
                tmp = tmp1 = tmp2 = "";
                for(int k = 1; k <= j; ++k)
                    tmp1 += s[k - 1];
                for(int k = j + 1; k <= l; ++k)
                    tmp2 += s[k - 1];
                tmp += tmp1, tmp += '#', tmp += tmp2;
                H.insert(tmp);
            }
        }
    }
    for(int i = 1; i <= m; ++i){
        s = srd();
        if(H.find(s)){
            printf("-1\n");
            continue;
        }
        int l = s.size(), ans = 0;
        tmp = s;
        for(int j = 0; j < l; ++j){
            tmp[j] = '#';
            ans += H.find(tmp);
            if(j == l - 1 || s[j] != s[j + 1]){// 只添加最后一个
                tmp[j] = '#';
                ans += H.find(tmp);
            }
            tmp[j] = s[j];
        }
        if(l < 20){
            for(int j = 0; j <= l; ++j){
                tmp = tmp1 = tmp2 = "";
                for(int k = 1; k <= j; ++k)
                    tmp1 += s[k - 1];
                for(int k = j + 1; k <= l; ++k)
                    tmp2 += s[k - 1];
                tmp += tmp1, tmp += '#',tmp += tmp2;
                ans += H.find(tmp);
            }
        }
            
        printf("%d\n", ans);
    }
	return 0;
}

标签：Hash,题解,ll,枚举,一位,插入,电子字典,P4407,字母
From： https://www.cnblogs.com/cotsheep/p/16878240.html