K-hash
64-bit integer IO format: %lld Java class name: Main
K-hash is a simple string hash function. It encodes a string Sconsist of digit characters into a K-dimensional vector (h0, h1, h2,... , hK-1). If a nonnegative number x occurs in S, then we call x is S-holded. And hi is the number of nonnegative numbers which are S-holded and congruent with i modulo K, for i from 0 to K-1.
For example, S is "22014" and K=3. There are 12 nonnegative numbers are "22014"-holded: 0, 1, 2, 4, 14, 20, 22, 201, 220, 2014, 2201 and 22014. And three of them, 0, 201 and 22014, are congruent with 0 modulo K, so h0=3. Similarly, h1=5 (1, 4, 22, 220 and 2014 are congruent with 1 modulo 3), h2=4(2, 14, 20 and 2201 are congruent with 2 modulo 3). So the 3-hash of "22014" is (3, 5, 4).
Please calculate the K-hash value of the given string S.
Input
There are multiple cases. Each case is a string S and a integer number K. (S is a string consist of '0', '1', '2', ... , '9' , 0< |S| ≤ 50000, 0< K≤ 32)
Output
For each case, print K numbers (h0, h1, h2,... , hK-1 ) in one line.
Sample Input
123456789 10 10203040506007 13 12345678987654321 2 112123123412345123456123456712345678123456789 17 3333333333333333333333333333 11
Sample Output
0 1 2 3 4 5 6 7 8 9 3 5 5 4 3 2 8 3 5 4 2 8 4 68 77 57 58 59 53 49 57 60 55 51 45 59 55 53 49 56 42 57 14 0 0 14 0 0 0 0 0 0 0
Source
Author
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 351000; 4 struct SAM { 5 struct node { 6 int son[26],f,len; 7 void init() { 8 f = -1; 9 len = 0; 10 memset(son,-1,sizeof son); 11 } 12 } s[maxn<<1]; 13 int tot,last; 14 void init() { 15 tot = last = 0; 16 s[tot++].init(); 17 } 18 int newnode() { 19 s[tot].init(); 20 return tot++; 21 } 22 void extend(int c){ 23 int np = newnode(),p = last; 24 s[np].len = s[p].len + 1; 25 while(p != -1 && s[p].son[c] == -1){ 26 s[p].son[c] = np; 27 p = s[p].f; 28 } 29 if(p == -1) s[np].f = 0; 30 else{ 31 int q = s[p].son[c]; 32 if(s[p].len + 1 == s[q].len) s[np].f = q; 33 else{ 34 int nq = newnode(); 35 s[nq] = s[q]; 36 s[nq].len = s[p].len + 1; 37 s[q].f = s[np].f = nq; 38 while(p != -1 && s[p].son[c] == q){ 39 s[p].son[c] = nq; 40 p = s[p].f; 41 } 42 } 43 } 44 last = np; 45 } 46 } sam; 47 queue<int>q; 48 int du[maxn],dp[maxn][32],ans[maxn],k; 49 char str[maxn]; 50 int main(){ 51 while(~scanf("%s%d",str,&k)) { 52 memset(du,0,sizeof du); 53 memset(ans,0,sizeof ans); 54 sam.init(); 55 for(int i = 0; str[i]; ++i) sam.extend(str[i] - '0'); 56 for(int i = 0; i < sam.tot; ++i) { 57 memset(dp[i],0,sizeof dp[i]); 58 for(int j = 0; j < 10; ++j) if(sam.s[i].son[j] != -1) ++du[sam.s[i].son[j]]; 59 } 60 //cout<<du[0]<<endl; 61 while(!q.empty()); 62 for(int i = 0; i < sam.tot; ++i) if(!du[i]) q.push(i); 63 dp[0][0] = 1; 64 while(!q.empty()) { 65 int u = q.front(); 66 q.pop(); 67 for(int i = 0; i < 10; ++i) { 68 int v = sam.s[u].son[i]; 69 if(v == -1) continue; 70 if(--du[v] == 0) q.push(v); 71 if(u == 0 && i == 0) continue; 72 for(int j = 0; j < k; ++j) 73 dp[v][(j*10 + i)%k] += dp[u][j]; 74 } 75 for(int i = 0; i < k; ++i) 76 ans[i] += dp[u][i]; 77 } 78 ans[0]--; 79 for(int i = 0; str[i]; ++i) 80 if(str[i] == '0') { 81 ans[0]++; 82 break; 83 } 84 for(int i = 0; i < k-1; ++i) 85 printf("%d ",ans[i]); 86 printf("%d ",ans[k-1]); 87 } 88 return 0; 89 }