uva 10391 Compound Words

哈希

题意简短：单case，输入一列单词即一个字典，已经按字典序排好输入，上限为120000，然后要你找一些单词，这种单词可以分为两部分，两部分都是字典里面的单词，按字典序输出这种单词

很裸的哈希，对于每个单词，将其分成两部分，一共有len中分法，然后去查找是否都在字典中，如果都在字典中就输出（因为输入已经按字典序排好，扫描时直接扫下来就可以了，找到合适的就输出）

问题的关键就转变为，给你一个单词，怎么判断这个单词是不是在字典中，用哈希就可以快速判断到。输入时随便将每个单词都用哈希函数映射掉，每得到要查询的单词也直接映射过去查找

处理冲突的方法是链表（静态链表数组模拟）

用了BKDHash函数在处理字符串的映射

 

BKDHash，40ms

#include 
#include 
#define N 120000
#define LEN 110
#define P 0x7fffffffint n,tot;
char word[N+10][LEN];
int head[N+10];
struct list
{int n;int next;
}e[N+10];void add(unsigned int index ,int m)
{e[tot].n = m;e[tot].next = head[index];head[index] = tot++;
}unsigned int BKDHash(char *str)
{unsigned int seed = 131;unsigned int hash = 0;int len = strlen(str);for(int i=0; i)hash = hash * seed + str[i];return (hash & P) % N;
}int find(char *str)
{unsigned int index = BKDHash(str);for(int k=head[index]; k!=-1; k=e[k].next){int m = e[k].n;if(!strcmp(word[m] , str))return k;}return -1;
}int main()
{n = tot = 0;memset(head,-1,sizeof(head));while(scanf("%s",word[n])!=EOF){unsigned int index = BKDHash(word[n]);add(index , n);n++;}for(int i=0; i){char str1[LEN] , str2[LEN];int len = strlen(word[i]);for(int j=0; j1; j++){int k,kk;for(k=0,kk=0; kk<=j; k++,kk++)str1[k] = word[i][kk];str1[k] = '';for(k=0,kk=j+1; kk)str2[k] = word[i][kk];str2[k] = '';int ok[2];ok[0] = find(str1);ok[1] = find(str2);if(ok[0] != -1 && ok[1] != -1){printf("%s
",word[i]);break;}}}return 0;
}

 

 

自己瞎比比写的一个字符串哈希，冲突死了，200ms

#include 
#include 
#define N 120000
#define LEN 110int n,tot;
char word[N+10][LEN];
int head[N+10];
struct list
{int n;int next;
}e[N+10];void add(int index ,int m)
{e[tot].n = m;e[tot].next = head[index];head[index] = tot++;
}int Hash(int m)
{int len = strlen(word[m]);int sum = 0;for(int i=0; i)sum += (word[m][i] - 'a')*i;return sum%N;
}int find(char *str)
{int len = strlen(str);int sum = 0;for(int i=0; i)sum += (str[i] - 'a')*i;int index = sum%N;for(int k=head[index]; k!=-1; k=e[k].next){int m = e[k].n;if(!strcmp(word[m] , str))return k;}return -1;
}int main()
{n = tot = 0;memset(head,-1,sizeof(head));while(scanf("%s",word[n])!=EOF){int index = Hash(n);add(index , n);n++;}for(int i=0; i){char str1[LEN] , str2[LEN];int len = strlen(word[i]);for(int j=0; j1; j++){int k,kk;for(k=0,kk=0; kk<=j; k++,kk++) str1[k] = word[i][kk];str1[k] = '';for(k=0,kk=j+1; kk word[i][kk];str2[k] = '';int ok[2];ok[0] = find(str1);ok[1] = find(str2);if(ok[0] != -1 && ok[1] != -1){printf("%s
",word[i]);break;}}}return 0;
}