poj-1200

#include <stdio.h>
 #include <string.h>
 #include <stdlib.h>

 #define MAX_SUBSTRING_NUM 1600000
 #define BIG_PRIME 1000007
 #define MAX_N 25
 char baseString[3000000];

 struct NodeInfo{
     char val[MAX_N];
     int next;
 };

 typedef struct NodeInfo NodeInfo;

 int bucket[BIG_PRIME];
 NodeInfo storage[MAX_SUBSTRING_NUM];
 int storageFreeIndex;

 int hash(char * str, int length) {
     long long add = 0;
     for (long i = 0; i < length; i++) {
         add += str[i] * str[i];
     }
     return add%BIG_PRIME;
 }

 int ELFhash(char *key, int M)
 {
     unsigned int h=0;
     while(*key)
     {
         h=(h<<4)+ *key++;
         unsigned int g= h&0xF0000000;
         if(g) h^=g>>24;
         h&=~g;
     }
     return h%M;
 }

 // char checkSubString(long begin, long end, char * baseString) {
 //     char tmpArray[MAX_N] = {0};
 //     long length = end - begin + 1;
 //     memcpy(tmpArray, baseString + begin, length);
 //     // printf("checkSubString %s\n", tmpArray);
 //     int hval = hash(tmpArray, length);
 //     NodeInfo * current = hashMap[hval];
 //     while(current) {
 //         if (!strcmp(current->val, tmpArray)) {
 //             return 0;
 //         }
 //         current = current->next;
 //     }
 //     NodeInfo * prev = hashMap[hval];
 //     NodeInfo * newNode = (NodeInfo *)malloc(sizeof(NodeInfo));
 //     memset(newNode, 0, sizeof(NodeInfo));
 //     memcpy(newNode->val, tmpArray, length);
 //     hashMap[hval] = newNode;
 //     hashMap[hval]->next = prev;
 //     return 1;
 // }

 char checkSubStringStatic(long begin, long end, char * baseString) {
     char tmpArray[MAX_N] = {0};
     long length = end - begin + 1;
     memcpy(tmpArray, baseString + begin, length);
     int hval = ELFhash(tmpArray, BIG_PRIME);
     // printf("checkSubString %s %d\n", tmpArray, hval);
     if (bucket[hval]) {
         int currId = bucket[hval];
         while(currId) {
             // printf("currId %d %s %s\n", currId, tmpArray, storage[currId].val);
             if (!strcmp(tmpArray, storage[currId].val)) {
                 return 0;
             }
             currId = storage[currId].next;
         }
         int prev = bucket[hval];
         bucket[hval] = storageFreeIndex++;
         memset(&(storage[bucket[hval]]), 0, sizeof(NodeInfo));
         storage[bucket[hval]].next = prev;
         memcpy(storage[bucket[hval]].val, tmpArray, length);
         return 1;
     } else {
         // printf("first %d %s\n", storageFreeIndex, tmpArray);
         bucket[hval] = storageFreeIndex++;
         memset(&(storage[bucket[hval]]), 0, sizeof(NodeInfo));
         storage[bucket[hval]].next = 0;
         memcpy(storage[bucket[hval]].val, tmpArray, length);
         return 1;
     }
 }

 long long getCombineNum(int N, int NC, char * baseString) {
     long length = strlen(baseString);
     long long combine_num = 0;
     if (length < N) {
         return 0;
     }
     // long long max_combine_num = 1;
     // for (int i = 1; i <= N; i++) {
     //     max_combine_num *= NC;
     // }

     for (long i = 0; i <= (length - 1) - N + 1; i++) {
         long end = i + N -1;
         combine_num += checkSubStringStatic(i, end, baseString);
         // if (combine_num >= max_combine_num) {
         //     return combine_num;
         // }
     }
     return combine_num;
 }
 int main() {
     int N = 0;
     int NC = 0;
     // while(scanf("%d %d", &N, &NC) != EOF) {
         scanf("%d %d", &N, &NC);
         scanf("%s", baseString);
         memset(storage, 0, sizeof(storage));
         memset(bucket, 0, sizeof(bucket));
         storageFreeIndex = 1;
         printf("%lld\n", getCombineNum(N, NC, baseString));
     // }
 }

55096K 219MS

这道题从时间倾向上不是用传统的hash数组法解，而是采用一种转换进制办法（每一种字符对应进制的一个数，２０种字符就是20进制）来解，以后要做一下，现阶段正在练hash，

先用常规的hash法，一开始用了拉链法hash，结果又犯了malloc以后没有memset 0， 在struct里面有char数组的情况下 :(.

排除了以后，TLE，:(.

不得不参考了别人的搞法，发现了一种静态模仿拉链hash的办法 :).

做法其实和动态拉链hash思想上是一样，只不过这次如果再有碰撞，直接从预分配的大hashnode数组上找第一个空闲的就可以。

这样就避免了malloc以及间接寻址的开销，具体做法是，先开一个int数组 bucket，大小是hash桶的大小，一般就是一个大质数。

然后是开一个能够保证容下所有不同元素的node数组NodeArray（每个node记录实际的字符串信息和next）。

一开始bucket每个hash对应的值都是0，代表此hash对应的node一个都没有（因为用0判定，所以我把nodeArray的freeIndex设为1，浪费一个node空间，在node数组空间要额外加1，最保险），然后在加入新的元素时，通过hash算出在bucket中的位置i，

如果bucket[i] == 0，代表还没有node映射到此hash值上，那么在nodeArray中找一个最小的没用被占用的node(ｋ)保存此node信息，bucket[i]设置为k, 而nodeArray[k]的next设为0, val设为对应的字符串。

如果bucket[i] !=0 说明已经有node映射到此hash值了，那么就根据next进行遍历比较val, 如果存在，那么直接返回０，如果遍历一遍还没有，那么就插入一个新的node。

上面这些操作其实本质和动态指针拉链没啥区别。想明白了，本质都是一样的，只不过一个用真正的指针只想一块内存，　另一个用一个索引值指向预分配数组的某一个位置.

和静态tire树很相似，以后在遇到类似分配动态内存的时候为了提高效率都可以考虑这种预分配数组加索引值的办法.

一开始用的自己写的傻瓜式平方和hash，TLE :(.

后来换成了ELFHash, AC了，　看样子hash函数选择也是很重要的.