|
题意：问有多少个单词有2个单词组成
题解：由于串很多，但是单词很短，那么我们直接分解单词就好啦，每个位置枚举可能，那么我们只要在词库里面找这2个单词就好啦，现在需要设计一个高效的算法快速找到单词
1：map 查找速度logN
2：hash表，将单词hash后在数组里面查找，如果足够离散那么平均的时间复杂度应该是能达到O(1)的查找速度，我使用的是SDBMHash函数，这个函数相当其他的hash函数离散的表现最好，冲突少，也可以直接使用STL的hash函数，不过要支持c++11才可以使用。这里给出2种解法
模板
unsigned int gethash(const string &st)//SDBMHash
{
unsigned int Hash = 0;
for (int i = 0; i < st.size(); i++)
{
Hash = (st[i]) + (Hash << 6) + (Hash << 16) - Hash;
}
return (Hash & 0x7FFFFFFF)%mod;
}
void insert(const string &st)
{
int c = HASH(st)%mod;
str[cnt] = st;
Next[cnt] = head[c];
head[c] = cnt++;
}
bool find(const string &st)
{
int c = HASH(st)%mod;
for (int i = head[c]; i != -1; i = Next[i])
{
if (str[i] == st)
return true;
}
return false;
}
手写hash表：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<bitset>
#include<utility>
#include<functional>
#include<iomanip>
#include<sstream>
#include<ctime>
using namespace std;
typedef long long LL;
enum { N = int(1e6+10) ,inf=int(0x3f3f3f3f),mod =int(1e6+3) };
string s,str[N];
int head[N], Next[N];
int cnt;
void init()
{
cnt = 0;
memset(head, -1, sizeof(head));
}
unsigned int gethash(const string &st)//SDBMHash
{
unsigned int Hash = 0;
for (int i = 0; i < st.size(); i++)
{
Hash = (st[i]) + (Hash << 6) + (Hash << 16) - Hash;
}
return (Hash & 0x7FFFFFFF)%mod;
}
void insert(const string &st)
{
int c = gethash(st);
str[cnt] = st;
Next[cnt] = head[c];
head[c] = cnt++;
}
bool find(const string &st)
{
int c = gethash(st);
for (int i = head[c]; i != -1; i = Next[i])
{
if (str[i] == st)
return true;
}
return false;
}
int main()
{
#ifdef CDZSC
freopen("i.txt", "r", stdin);
//freopen("o.txt","w",stdout);
int _time_jc = clock();
#endif
ios::sync_with_stdio(false);
string tmp1,tmp2;
init();
while (cin >> s)insert(s);
for (int i = 0; i < cnt; i++)
{
for (int k = 1; k < str[i].size(); k++)
{
tmp1 = str[i].substr(0, k);
tmp2 = str[i].substr(k, str[i].size() - k);
if (find(tmp1) && find(tmp2))
{
cout << str[i] << endl;
break;
}
}
}
return 0;
}
STL的Hash函数，需要c++11标准支持才能用
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<bitset>
#include<utility>
#include<functional>
#include<iomanip>
#include<sstream>
#include<ctime>
using namespace std;
typedef long long LL;
enum { N = int(1e6+10) ,inf=int(0x3f3f3f3f),mod =int(1e6+3) };
string s,str[N];
int head[N], Next[N];
int cnt;
void init()
{
cnt = 0;
memset(head, -1, sizeof(head));
}
hash<string>HASH;
void insert(const string &st)
{
int c = HASH(st)%mod;
str[cnt] = st;
Next[cnt] = head[c];
head[c] = cnt++;
}
bool find(const string &st)
{
int c = HASH(st)%mod;
for (int i = head[c]; i != -1; i = Next[i])
{
if (str[i] == st)
return true;
}
return false;
}
int main()
{
#ifdef CDZSC
freopen("i.txt", "r", stdin);
//freopen("o.txt","w",stdout);
int _time_jc = clock();
#endif
ios::sync_with_stdio(false);
string tmp1,tmp2;
init();
while (cin >> s)insert(s);
for (int i = 0; i < cnt; i++)
{
for (int k = 1; k < str[i].size(); k++)
{
tmp1 = str[i].substr(0, k);
tmp2 = str[i].substr(k, str[i].size() - k);
if (find(tmp1) && find(tmp2))
{
cout << str[i] << endl;
break;
}
}
}
return 0;
}
| 
转播
