Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### KimJennie's blog

By KimJennie, history, 7 weeks ago,

Hello, Codeforces!

I have next task: given string s and t. And I have to find does s contains t, and if yes, I should print the first i that [i..i+t.size()-1] = t How can I do it? I counted hash from all t in variable(hsh += (t[i] - 'a' + 1) * ppow) and hash from s in array (h[i] = (s[i] - 'a' + 1) * p_pow[i]). So I run from 0 to s.size()-t.size() and count hash in [l;r] using formula h(s[l:r]) = (h[r]-h[l])/p^l. But when s = "ab" and i count hash where l = 0, r = 1, I got 62, not 63. Where is my mistake? Please help me

• 0

 » 7 weeks ago, # |   0 I think that h(s[l:r]) = h[r] - h[l-1] * p ^ (r-l+1)
•  » » 7 weeks ago, # ^ |   0 What if l = 0? Or I should 1-numerate?
•  » » » 7 weeks ago, # ^ |   0 1-numerate, or h[-1] = 0 .
•  » » » » 7 weeks ago, # ^ |   0 s = "abaaba" when you count l = 2, r = 2 you got -927, but answer is 2. How can I fix it?
•  » » » » » 7 weeks ago, # ^ |   0 I think you have something wrong.My core Code (in C++): typedef long long ll; const int N = 555; const ll P = 999999999999989, base = 131; typedef char str[N]; int n, m; ll pb[N]; ll mul(ll A, ll B) // O(log) { ll ans = 0; while (B) { if (B & 1) ans = (ans + A) % P; B >>= 1; A = (A + A) % P; } return ans; } void init() { pb[0] = 1; for (int i=1; i
•  » » » » » » 7 weeks ago, # ^ |   0 I wrote simple code, so can you please check what's wrong? Here it is: https://pastebin.com/FZMTgm1M Let s be "ababa", and t be "ba" h(s[1:2]) = h(t), isn't it? But my output for h(s[1:2]) is -59519. Please help me
 » 7 weeks ago, # |   -6 count hashs of all prefixes. then write down hash of prefix with size r and prefix with size l — 1. And think what you need to do to get hash of s[l:r]
 » 7 weeks ago, # |   0 Your formula $\dfrac{h_r - h_l}{p^l}$ actually works if you use half-open intervals $[l, r)$. If you want to use them, make $h_0 = 0$ and $h_{i + 1} = h_i + hash(s_i) ^ i$ if $0 \le i < n$ (in 0-indexing). Notice, that now there are $n + 1$ elements in $h$. Then, if you are given queries $[l, r]$ (segment, in 0-indexing), increase $r$ by $1$ and use your formula.