字符串hash

2019-04-14 18:46发布

站内文章 / 模拟电子
13521 0 1425
//HDU4622 #include #include #include #include #include #include using namespace std ; //哈希函数的模 const int HASH = 10007 ; const int maxn = 2010 ; //哈希表结构 struct HASHMap{ //head使用HASH大小因为head开头是已经取摸HASH的数 //size扩展next int head[HASH] , next[maxn] , size ; //next[i]对应存放的数字为state unsigned long long state[maxn] ; //f[i]存储state[i]出现的最大的开始位置 int f[maxn] ; void init(){ size = 0 ; memset(head , -1 , sizeof( head )) ; } int insert( unsigned long long val , int id){ //哈希函数,h为val应该放的位置 int h = val%HASH ; for ( int i = head[h] ; i != -1 ;i = next[i] ) //如果val之前存在，返回之前val出现的起始位置，更新当前为最大的位置 //因为要保证val相等，必须字符的长度要想等，所以在main函数枚举的时候要长度在外循环 //所以相同字符串一定长度相同，在给定的长度L下，他们在第二个循环的时候就已经全部找出， //则一旦相同则当前的id值一定比之前的大，所以f[i] = id if( val == state[i]){ int temp = f[i] ; f[i] = id ; return temp ; } //否则建立新节点，返回下标0是一个无用的下标 f[size] = id ; state[size] = val ; next[size] = head[h] ; head[h] = size ++ ; return 0 ; } } H ; //将字符串转换成seed进制的数 const int seed = 13331 ; //p表示位权 unsigned long long p[maxn] ; //s表示字符串str的前缀的数值 unsigned long long s[maxn] ; char str[maxn] ; int ans[maxn][maxn] ; int main(){ //求seed进制的位权p p[0] = 1 ; for(int i = 1 ;i1] * seed ; int T; scanf("%d" , & T) ; while( T--) { scanf("%s" , str) ; int n = strlen (str) ; //将字符串转换成seed进制的整数 //求str前缀对应的 s[0] = 0 ; for(int i = 1 ; i <=n ; i ++) s[i] = s[i-1] * seed + str[i-1] ; memset( ans , 0 , sizeof( ans )) ; //枚举字符子串的长 //ans 表示i起点L长的子串， +1 表示存在一个i起点L长的子串， -1 表示有重复，-1之后能够保证整个字符串该子串只有一个 for(int L = 1 ; L <= n ;L ++){ H.init() ; for(int i = 1 ; i+L -1 <= n ;i++){ //[i , i+L-1} 区间的字符子串的哈希值大小为 s[i+L - 1] - s [i]*p[L] // s [i]*p[L] 这个相当于把s[i] 增大p[L] 倍 //就比如说十进制字符串" 123 " //字符子串" 23 " 的大小是 2*10 + 3 //如果使用 s[i]*10 + s[i+1] 这样的连续处理虽然可以但是复杂度太高 //要在线性获得23 ， 我们就要预处理前缀字符串大小1 12 123 //2到3位的字符串大小为 123 - 1* 100 = 23 , //使用的公式就是 s[i+L-1] - s[i-1]* p[L] L 代表字符串的长度2， int l = H.insert( s[i+L-1] - s[i-1]* p[L] , i) ; // +1 表示为获得一个子串 ans[i][i+L -1 ] ++ ; //-1表示重复了一个子串，但是因为每次都有ans[i][i+L-1]++ ， 所以总体ans的和就是整个字符串不重复子串的个数 ans[l][i+L-1] -- ; } } //对于字符串str、 //他的[i,...n] 也就是从i开始的后缀的所有不相同的子串的个数就是ans从i开始到n结束的整个矩形所有数值的和 //对于字符串aab举例 //他的ans如下 /* 0 -1 -1 -3 0 1 0 1 0 0 1 1 0 0 0 1 */ //我们可以验证之前的结论 //那么要获得任意i,j区间范围的不同字符串的个数我们就要用下面的递推 //要求任意i，j区间的不同子串的个数 target[i][j] ，实际上就是求ans的i行j列的左下角和边界所有数值的和 //由递推公式有 ans[i][j] + ans[i+1][j] + ans[i][j-1] - ans[i+1][j-1] ; for( int i = n ;i>= 1 ;i--){ //i<=j 因为是(i,j) 范围字符串 for(int j = i ;j<=n ;j++){ //（i，j）不重复子串的个数计算公式 ans[i][j] += ans[i+1][j] + ans[i][j-1] - ans[i+1][j-1] ; } } int m , u , v ; scanf("%d" , & m ) ; while( m-- ){ scanf("%d%d" , & u , & v) ; printf("%d " , ans[u][v]) ; } } return 0 ; }

热门文章