N - 韩爷的梦

Time Limit: 200/100MS (Java/Others) Memory Limit: 1300/1300KB (Java/Others)

Submit Status

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

韩爷前晚没睡好，随手写了一个程序交给面试官，然后就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;

}

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

Input

单case

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

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

Output

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

Sample input and output

aaAa

aaAa

bbbb

1234

bbbb

bbbb

ee09

Hint

样例只是样例，不在test中

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

解题报告:

直接上哈希即可，双哈希单哈希都可以过，如果过不了，请换素数。。。。囧

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

const int maxn = 2e4 + 100;

char str[maxn];

void hashinit(int &x1,int &x2)

{

   x1 = 0x7FED7FED , x2 = 1;

   int p1 = 1526597;

   int p2 = 89834777;

   int mod1 = 1e9 + 7;

   int mod2 = 1e9 + 9;

   unsigned int x3 = 0x23322322;

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

    {

       int val = str[i];

       x1 = (x1*p1 + val)%mod1;

	}

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

   {

   	   int val = str[i];

   	   x2 = (x2*p2 + val)%mod2;

   }

}

int main(int argc,char *argv[])

{

  int  hash1[maxn];

  int  hash2[maxn];

  int size = 0;

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

   {

   	  scanf("%s",str+1);

   	  int q1,q2;

   	  hashinit(q1,q2);

   	  hash1[size] = q1,

   	  hash2[size++] = q2;

   }

  sort(hash1,hash1+size);

  sort(hash2,hash2+size);

  int c1 = unique(hash1,hash1+size) - hash1;

  int c2 = unique(hash2,hash2+size) - hash2;

  printf("%d\n",min(c1,c2));

  return 0;

}