题目：

思路：

如果直接暴力搜索的话，时间复杂度为O(n*m)，在n为百万量级的情况下，必然是T。

所以，这里通过hash函数，将字符串转换为对应的hash值；同时利用邻接表避免了hash冲突，方法是用head[hashval]存储指向一个相同hash值的单链表的指针(这里指的是相当于一个头指针)，如果一个字符串得到的hash值在之前出现过，则加入单链表；最后在查找的时候，只需要找字符串对应hash值的单链表即可。

注意：(1)在建立邻接表的时候，新插入的节点不断加入到链表的首部，这样在查询的时候，刚好是相反的。(2)hash函数选用IndexHash。

时间复杂度O(n)。

代码：

////  main.cpp//  searchme////  Created by wasdns on 16/12/12.//  Copyright © 2016年 wasdns. All rights reserved.//#include 
    
     #include 
     
      #include 
      
       #define mod 999983                          //int范围内取最大的素数#define maxn 1000005using namespace std;/*    Hash函数：IndexHash */int IndexHash(char *s){    int hashval = 0;        while (*s != '\0') {        hashval = (hashval << 5) + *s++;    }        return hashval % mod;}char searchname[maxn][10];                  //你的名字int head[maxn];                             //邻接表的头数组int lnext[maxn];                            //邻接表的节点数组int tot = 1;                                //第tot个字符串/*    AddNode创建邻接表函数：        在head[hashval]中存指向单链表的指针        插入时，现有head的值存入lnext[tot]        之后使head[hashval]成为新的节点        相当于不断在链表的首部进行插入 */void AddNode(int hashval){    lnext[tot] = head[hashval];        head[hashval] = tot;        tot++;}/*    询问函数：        通过IndexHash得到hash值        利用head[hashval]找到指向对应hash值的单链表        遍历单链表，找到 -> 计数器++。 */void query(int q){    int cnt = 0;        for (int i = 1; i <= q; i++)    {        int hashval = 0;                char findname[10];                scanf("%s", findname);                hashval = IndexHash(findname);                for (int j = head[hashval]; j != -1; j = lnext[j])        {            if (strcmp(searchname[j], findname) == 0) {                cnt++;            }        }    }        printf("%d\n", cnt);}int main(){    memset(head, -1, sizeof(head));    memset(lnext, -1, sizeof(lnext));        int n, m;        cin >> n >> m;        int i;        for (i = 1; i <= n; i++)    {        scanf("%s", searchname[i]);                int hashval = IndexHash(searchname[i]);                AddNode(hashval);    }        cout << endl;        query(m);        return 0;}
      
     
    

2016/12/12