해시 처리 문자열

자주 사용 하 는 해시 함수, seed = 131, 단계 배열 초기 화, 편리 등 단계 후 비교, 문자열 초기 화, 비교 시 차이 만 볼 수 있 습 니 다.

역방향 으로 문자열 을 초기 화하 여 현재 요 소 를 차이 점 에 있 게 합 니 다.

#define L 100000
int seed = 131;
ULL base[L+5];
ULL hv[L+5];
char str[L+5];
int len;

void initBase()
{
    base[0] = 1;
    for(int i = 1; i <= L; ++i)
        base[i] = base[i-1]*seed;
}
void initHv()
{
    len = strlen(str);
    hv[len] = 0;
    for(int i = len-1; i >= 0; --i)
        hv[i] = hv[i+1]*seed + str[i];
}
ULL getHash(int x, int l)
{
   return hv[x] - hv[x+l]*base[l];
}