2015 UESTC 搜索专题N题 韩爷的梦 hash

时间：2023-03-09 22:35:56
2015 UESTC 搜索专题N题 韩爷的梦 hash

韩爷的梦

Time Limit: 20 Sec  Memory Limit: 256 MB

题目连接

http://acm.uestc.edu.cn/#/contest/show/61

Description

一天，韩爷去百度面试，面试官给了他这么一个问题。

给你2万个字符串，每个字符串长度都是100，然后把2万个字符串丢入一个 set< string >g 中，问最终set里含有多少个元素？
g 是一个用来存储字符串、具有去重功能的容器，即相同字符串在 g 中只能保留一个。
两个字符串相等，当且仅当，长度一样且对应位置的字符都一样。

韩爷前晚没睡好，随手写了一个程序交给面试官，然后就gg了。

#include<iostream>

#include<string>

#include<set>

using namespace std;

string s;

set<string>g;

int main(){

    for(int k=1;k<=20000;k++){

        cin>>s;

        g.insert(s);

    }

    cout<<g.size()<<endl;

    return 0;

}

韩爷醒来之后，发现这只是一个梦（还好只是个梦）。他回忆起梦中的面试官给他的内存限制和时间限制非常低，这么做肯定过不了，那么，现在你不在梦中，你能解决这个问题么？

A的某一段完全重合，或者能够经过上下左右平移与折线A的某一段完全重合，则表示秋实大哥吹出了妹子的一部分旋律。

Input

单case

每个case有且只有2万行，每一行包含一个字符串，每行字符串的长度都为100 （样例除外）

字符集：大写英文字母（A－Z），小写英文字母（a－z），数字（0－9）

Output

输出一个整数，表示最终set里含有多少个元素。

Sample Input

aaAa
aaAa
bbbb
1234
bbbb
bbbb
ee09

Sample Output

4

HINT

样例只是样例，不在test中

注意时间限制和内存限制非常低

题意

题解：

单hash一下就好

双hash也很稳

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 812361263

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

const int inf=0x3f3f3f3f;

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

inline ll read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

char s[];

vector<int > a;

/*

int ELFhash(char *key){

    unsigned long h=0;

    unsigned long x=0;

    while(*key)

    {

        h=(h<<4)+(*key++);  //h左移4位，当前字符ASCII存入h的低四位

                if( (x=h & 0xF0000000L)!=0)

        { //如果最高位不为0，则说明字符多余7个，如果不处理，再加第九个字符时，第一个字符会被移出

          //因此要有如下处理

          h^=(x>>24);

          //清空28~31位

          h&=~x;

        }

    }

    return h % mod;

}

*/

int get_hash(char *key)

{

    ll N=;

    long long h=;

    while(*key)

        h=(h*+(*key++)+N)%N;

    return h%N;

}

int main()

{

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

    {

        scanf("%s",s);

        a.push_back(get_hash(s));

    }

    sort(a.begin(),a.end());

    a.erase(unique(a.begin(),a.end()),a.end());

    printf("%d\n",a.size());

}

相关文章