学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1247

大意：给定字典序的一连串字符串，找出其中一个能由其他两个组成的字符串。

用这个题目练习下字符串hash，作为学习字符串hash，特地看了并转载了几篇博客。其中有人说BKDHash是较好记效率又蛮高的。

BKDHash代码：

/*
    为了处理hash值重叠的问题，需要额外开一个数组来存储每个hash值对应的字符串
    0x7fffffff为int的最大值
*/


int BKDHash(char *c)//哈希函数。
{
    int Hash=0;
    while(*c)
        Hash=Hash*31+(*c++);
	return(Hash&0x7FFFFFFF)%100000;//这里的 & 运算可以处理Hash越界为负值是的情况
}

显然一个，一个字符串a，可能又给定字符串中的b,c组成，我们可以枚举b,c。看组成的a是否在字典序中。时间复杂度O(n^2)。

还有另外一种，枚举a，把a拆成两个字符串b,c。看b,c是否在字典序中，显然要节约时间些。

代码：

//freopen("C:\\Documents and Settings\\All Users\\×ÀÃæ\\in.txt","w",stdout);

#include<iostream>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>

using namespace std;

vector<string> v[100000],V;

int BKDHash(char *c){
    int hash=0;
    while(*c) hash=hash*31+(*c++);
    return (hash&0x7fffffff)%100000;
}

int main(){
    string s;
    while(cin>>s && s!="!"){
        int t=BKDHash(&s[0]);
        v[t].push_back(s);
        V.push_back(s);
    }
    for(int i=0;i<V.size();i++){
        if(V[i].size()==1) continue;
        string s1,s2;
        for(int j=0;j<V[i].size()-1;j++){
            s1.clear();s2.clear();
            for(int k=0;k<=j;k++)
                s1+=V[i][k];
            for(int k=j+1;k<V[i].size();k++)
                s2+=V[i][k];
            int t1=BKDHash(&s1[0]),t2=BKDHash(&s2[0]);
            int op=0,op2=0;
            for(int p=0;p<v[t1].size();p++)
                if(v[t1][p]==s1){op=1;break;}
            for(int p=0;p<v[t2].size();p++)
                if(v[t2][p]==s2){op2=1;break;}
            if(op && op2){cout<<V[i]<<endl;break;}
        }
    }
    return 0;

}