POJ 3461 문자열 해시

//      ,    hash
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define ull unsigned long long
const ull B=1e8+7,C=1e8+119;
const int dmax=1000100;
char s[dmax],s1[dmax];

int hash(char *a,char *b){
	int ans=0,i;
	ull x=strlen(a),y=strlen(b),t=1,t1=1;
	ull ah=0,bh=0,al=0,bl=0;
	if (x>y)
		return 0;
	for (i=0;i<x;i++){
		t*=B,t1*=C;
		ah=ah*B+a[i],bh=bh*B+b[i];
		al=al*C+a[i],bl=bl*C+b[i];
	}
	for (i=0;i+x<=y;i++){
		if (al==bl && ah==bh)
			ans++;
		if (i+x<y){
			bh=bh*B-b[i]*t+b[i+x];
			bl=bl*C-b[i]*t1+b[i+x];
		}
	}
	return ans;
}

int main(){
	int T;
	scanf("%d",&T);
	getchar();
	while (T--){
		gets(s1);
		gets(s);
		printf("%d
",hash(s1,s)); } return 0; }

좋은 웹페이지 즐겨찾기