KimJennie's blog

How to find string hash in segment [l; r]
By KimJennie, history, 2 months ago, In English

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

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think that h(s[l:r]) = h[r] - h[l-1] * p ^ (r-l+1)

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What if l = 0? Or I should 1-numerate?

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      1-numerate, or h[-1] = 0 .

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        s = "abaaba" when you count l = 2, r = 2 you got -927, but answer is 2. How can I fix it?

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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<N; i++) pb[i] = mul(pb[i-1], base) % P;
}
struct HashS
{
	ll ph[N];
	ll hash(int l, int r)
	{
		ll sub = l ? ph[l-1] : 0;
		return (ph[r] - mul(sub, pb[r-l+1]) + P) % P;
	}
	inline explicit HashS(const str& s)
	{
		ph[0] = s[0];
		for (int i=1; i<m; i++) ph[i] = (mul(ph[i-1], base) + s[i]) % P;
	}
};
          → Reply
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

            → Reply
»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

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]

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply