字符串Hash的應用

題意：輸入一堆數字 看一堆數中最少有多少個上升子串（不連續的子串） 1個數字單獨也算一個子串。

[cpp] #include <iostream>  
#include <stdio.h>  
#include <string.h>  
 
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<<maxval<<endl; 
    } 
    return 0; 
} 

#include <iostream>
#include <stdio.h>
#include <string.h>

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<<maxval<<endl;
    }
    return 0;
}