hdu 4622 （hash+“map”）

题目链接：https://vjudge.net/problem/HDU-4622

题意：给定t组字符串每组m条询问——求问每条询问区间内有多少不同的子串。

题解：把每个询问区间的字符串hash一下存图，这样访问的复杂度就只有O(1).至于为什么不能用map查重我也不知道，用map+hash会超时。所以我们需要手动写个map(直接套用kuangbin大佬的模板)。最后只要利用二维前缀和即可输出答案。

Ac 代码：

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

#include<stack>

#include<cstdio>

#include<map>

#include<set>

#include<string>

#include<queue>

#define memt(a,b)  memset(a,b,sizeof a)

using namespace std;

typedef unsigned long long ull;

const int M = 1e4+7;

const int maxn = 2e3+10;

const int base = 13331;

struct HASHMAP {         //构造map，直接用map会tle(套用kuangbin大佬模板);

    int head[M],next[maxn],size;

    ull state[maxn];

    int f[maxn];

    void init(){

        size = 0;

        memt(head,-1);

    }

    int insert(ull val,int _id) {

        int h = val%M;

        for(int i = head[h]; i != -1; i = next[i])

            if(val == state[i]){

                int tmp = f[i];

                f[i] = _id;

                return tmp;

            }

        f[size] = _id;

        state[size] = val;

        next[size] = head[h];

        head[h] = size++;

        return 0;

    }

} H;

ull P[maxn];   //种子;

ull S[maxn];   //存hash值;

char str[maxn];

int ans[maxn][maxn];    //存图查重;

int main() {

    P[0] = 1;

    for(int i = 1; i < maxn; i++)  P[i] = P[i-1] * base;

    int T;

    cin>>T;

    while(T--){

        scanf("%s",str);

        int n = strlen(str);

        S[0] = 0;

        for(int i = 1; i <= n; i++)  S[i] = S[i-1]*base + str[i-1];

        memt(ans,0);

        for(int L = 1; L <= n; L++){

            H.init();

            for(int i = 1; i + L - 1 <= n; i++){

                //返回的是这个长度的串之前出现的位置，之前出现过，所以在那个位置到

                //当前这个位置这段区间的个数要减-1，同一个区间内同样的串只需要计算一次

                int l = H.insert(S[i+L-1] - S[i-1]*P[L],i);

                ans[i][i+L-1]++;

                ans[l][i+L-1]--;

            }

        }

        for(int i = n; i >= 0; i--)

            for(int j = i; j <= n; j++)

                ans[i][j] += ans[i+1][j] + ans[i][j-1] - ans[i+1][j-1];//二维前缀和;

        int m,u,v;

        cin>>m;

        while(m--){

            cin>>u>>v;

            cout<<ans[u][v]<<endl;

        }

    }

    return 0;

}

巴特西

hdu 4622 （hash+“map”）

最新文章

热门文章