字符串Hash的应用

题意：输入一堆数字 看一堆数中最少有多少个上升子串（不连续的子串） 1个数字单独也算一个子串。

[cpp] #include
#include
#include

using namespace std;
const int N = 7003;

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

int hash[N],count[N];
int maxval,n;

void hashhit(char *str)
{
int k,t;
while(*str=='0') str++;
k=ELFhash(str);
t=k%N;
while(hash[t]!=k&&hash[t]!=-1)
t=(t+10)%N;
if(hash[t]==-1) count[t]=1,hash[t]=k;
else if(++count[t]>maxval) maxval=count[t];
}

int main()
{
char str[105];
while(cin>>n)
{
memset(hash,-1,sizeof(hash));
maxval=1;
while(n--)
{
cin>>str;
hashhit(str);
}
cout< }
return 0;
}

#include
#include
#include

using namespace std;
const int N = 7003;

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

int hash[N],count[N];
int maxval,n;

void hashhit(char *str)
{
int k,t;
while(*str=='0') str++;
k=ELFhash(str);
t=k%N;
while(hash[t]!=k&&hash[t]!=-1)
t=(t+10)%N;
if(hash[t]==-1) count[t]=1,hash[t]=k;
else if(++count[t]>maxval) maxval=count[t];
}

int main()
{
char str[105];
while(cin>>n)
{
memset(hash,-1,sizeof(hash));
maxval=1;
while(n--)
{
cin>>str;
hashhit(str);
}
cout< }
return 0;
}