데이터 구조 기록 - 산열 법 실험

Home
Web Board
ProblemSet
Standing
Status
Statistics
Problem A: 산열 법의 실험
Time Limit: 1 Sec  
Memory Limit: 128 MB
Submit: 1008  
Solved: 310
[ Submit][ Status][ Web Board]
Description
산열 법 에 서 는 산열 함수 구조 방법 이 다양 하 며 같은 산열 함수 에 대해 충돌 을 해결 하 는 방법 도 다 를 수 있다.두 가 지 는 검색 알고리즘 의 성능 에 영향 을 주 는 관건 적 인 요소 이다.다음 해시 함수 로 문자열 해시 값 을 계산 합 니 다.H(key) = (s[0] * 31^(n – 1) + s[1] * 31 ^ (n – 2) + ….. + s[n – 1] * 31 ^ 0) % mod; 여기 서 ^ 곱셈, s [i] 문 자 를 대표 하 는 ASCII 값 은 2 차 탐지 재 산열 방법 으로 충돌 을 처리 합 니 다 Hi = (H (key) + di)% mod di = 1, - 1, 4, - 4, 9, - 9, 16, - 16.각 그룹의 샘플 에 대해 첫 번 째 줄 은 두 개의 숫자 N 과 mod (그 중 1 < = N < = 1000, N < mod < = 2000, mod 는 소수 이 고 문자열 의 길 이 는 1000 보다 작 음) 를 입력 하 며 N 과 mod 는 각각 문자열 의 개수 와 모델 을 표시 합 니 다.다음 n 줄 은 줄 마다 소문 자 만 있 는 문자열 입 니 다.
Input
샘플 은 EOF 가 끝 날 때 까지 여러 그룹 을 포함한다.각 그룹의 샘플 에 대해 첫 번 째 줄 은 두 개의 숫자 N 과 mod (그 중 1 < = N < = 1000, N < mod < = 2000, mod 는 소수 이 고 문자열 의 길 이 는 1000 보다 작 음) 를 입력 하 며 N 과 mod 는 각각 문자열 의 개수 와 모델 을 표시 합 니 다.다음 n 줄 은 줄 마다 소문 자 만 있 는 문자열 입 니 다.
Output
해시 함수 에 저 장 된 모든 키 워드 를 순서대로 출력 합 니 다. (해시 값 에 따라 작은 출력 문자열 까지)
Sample Input
5 11rgfslwdrzmiugiobmernjumq
Sample Output
5 4 6 2 3
HINT
해시 값 계산 과정 에서 모델 링 에 주의해 야 합 니 다. 넘 칠 수 있 는 두 가지 모델 링 공식: (a + b)% mod = (a% mod + b% mod)% mod (a – b)% mod = (a% mod – b% mod + mod)% mod
Append Code
[ Submit][ Status][ Web Board]

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define m 10005
typedef string KeyType;
typedef struct
{
    KeyType key;
} HashTable;
long long int pow(int a,int b,int mod)
{
    long long int x=1,y=a;
    while(b)
    {
        if(b&0x1)
            x=x*y%mod;
        y=y*y%mod;
        b>>=1;
    }
    return x;
}
int H(string s,int mod)
{
    int key;
    long long int k=0;
    for(int i=0; i<s.length(); i++)
    {
        k+=(long long int)s[i]*pow(31,s.length()-1-i,mod);
    }
    key=k%mod;
    return key;
}
int put(HashTable *HT,string s,int n,int mod)
{
    int k=H(s,mod);
    int Hi=H(s,mod);
    if(HT[k].key.length()==0)
    {
        HT[k].key=s;
        return k;
    }
    else
    {
        for(int i=1; i<31; i++)
        {
            Hi = ( H(s,mod)% mod+ pow(i,2,mod)) % mod;
            if(HT[Hi].key.length()==0)
            {
                HT[Hi].key=s;
                return Hi;
            }
            else
            {
                Hi = ( H(s,mod)%mod- pow(i,2,mod)+mod) % mod ;
                if(HT[Hi].key.length()==0)
                {
                    HT[Hi].key=s;
                    return Hi;
                }
            }
        }
    }
}
int main()
{
    string st;
    int n,mod;
    while(scanf("%d %d",&n,&mod)!=EOF)
    {
        HashTable HT[m];
        int temp[n];
        for(int i=0; i<n; i++)
        {
            cin>>st;
            temp[i]=put(HT,st,n,mod);
        }
        for(int i=0; i<n; i++)
        {
            if(i==0)
                cout<<temp[i];
            else
                cout<<" "<<temp[i];
        }
        cout<<endl;
    }
}