|
传送门ZOJ :UVa 10391 & ZOJ 1825 - Compound Words
UVa: UVa
10391 & ZOJ 1825 - Compound Words
题意大家都懂。
其实这题和上一题差不多，区别在于最后查找的时候要把一个单词分成两部分来，如果这两部分在哈希表里都存在映射，就是复合词，输出。
#include <cstdio>
#include <cstring>
using namespace std;
const int HashSize = 200000;
char in[130000][30];
int head[HashSize], next[HashSize];
int BKDHash(char *c);
int Search(char *s);
void Insert(int s);
int main()
{
//freopen("input.txt", "r", stdin);
char str[30], temp[30];
int num = 1, i, j;
while (gets(in[num++]))
Insert(num - 1);
//sort(in + 1, in + num + 1);
for (i = 1; i <= num; i++)
for (j = 0; j < strlen(in[i]); j++)
{
for (int k = 0; k < j; k++)
temp[k] = in[i][k];
temp[j] = 0;
if (Search(temp) && Search(in[i] + j))
{
puts(in[i]);
break;
}
}
return 0;
}
int BKDHash(char *c) //哈希函数。
{
int seed = 131;
int Hash = 0;
for (int i = 0; i < strlen(c); i++)
Hash = Hash * seed + c[i];
return (Hash & 0x7FFFFFFF) % HashSize;
}
void Insert(int s)
{
int v = BKDHash(in[s]);
next[s] = head[v]; //插入到当前值的首部
head[v] = s;
}
int Search(char *s)
{
int v = BKDHash(s);
int u = head[v];
while (u)
{
if (strcmp(s, in[u]) == 0)
return 1;
u = next[u];
}
return 0;
}
| 
转播
