哈希函數 （處理字元串）

用哈希函數求區間值：

POJ 2752: Seek the Name, Seek the Fam

problem: http://poj.org/problem?id=2752

把每個字首和字尾相同的位置都輸出

Input:

ababcababababcabab
aaaaa
           

Output:

2 4 9 18
1 2 3 4 5
           

Code:

#include<iostream>
#include<cstring>
#include<cstdio>
#define rep(i,s,n) for(int i=s;i<=n;i++)
typedef unsigned long long ull; 
using namespace std;
const long long N = 4e5+10;

int len,flag;
char a[N];
ull p=233;
ull ha[N],d[N]={1}; //ull自動對2^64 - 1 取模

void f()
{
	rep(i,1,len) ha[i]=ha[i-1]*p+a[i-1];
	rep(i,1,len) d[i]=d[i-1]*p;
}

ull get_ha(int l, int r)
{
	return ha[r] - ha[l-1] * d[r-l+1];
}

int main()
{
	while(~scanf("%s",&a))
	{
		flag=0;
		len=strlen(a);
		f();
		rep(i,1,len)
		{
			if(get_ha(1,i) == get_ha(len+1-i,len))
			{
				if(!flag) printf("%d",i), flag=1;
				else printf(" %d",i);
			}
		}
		puts("");
	}
	
	return 0;	
}  
           

HDU 1686: Oulipo

problem: https://acm.hdu.edu.cn/showproblem.php?pid=1686

Input:

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
           

Output:

1
3
0
           

#include<iostream>
#include<cstring>
#include<cstdio>
#define rep(i,s,n) for(int i=s;i<=n;i++)
typedef unsigned long long ull;
using namespace std;
const long long N = 1e6+10;

int len,lenb,jishu,T;
char a[N],b[N];
ull p=233,ha_b;
ull ha[N],d[N]={1};

void f(char *a)
{
	len=strlen(a);
	rep(i,1,len) ha[i]=ha[i-1]*p+a[i-1];
	rep(i,1,len) d[i]=d[i-1]*p;
}

ull get_ha(int l, int r)
{
	return ha[r] - ha[l-1] * d[r-l+1];
}

int main()
{
	cin>>T;
	while(T--)
	{
		scanf("%s%s",&b,&a);
		lenb=strlen(b);
		rep(i,1,lenb) ha[i]=ha[i-1]*p+b[i-1];
		ha_b=ha[lenb];
		
		jishu=0;
		f(a);
		rep(i,1,len)
		{
			if(ha_b == get_ha(i,i+lenb-1)) jishu++;
			if(i+lenb-1 == len) break;	
		} 
		printf("%d\n",jishu);
	}
	
	return 0;	
}