redyellow's blog

solve 182D with hashing
By redyellow, 11 years ago, In English

http://codeforces.net/problemset/problem/182/D

this problem is tagged with hashing but i couldnt find any tutorial for it. can you please give me an idea for solving it by use of hashing? thanks.

  • Vote: I like it
  • -6
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Solution: find all divisors of each string, and find common of them.

How to find all divisors? We know that divisor D is prefix of string S and |S| = 0 (mod |D|). So, amount of divisors is at maximum sqrt(|S|). Let's check all prefixes of string which length is <= sqrt(|S|) and check if we write this prefix |S| / |D| times it will be same as S. If it is, then prefix D is the divisor of S. How to check it? Check if substring [0, |T|) is same as [|T|, 2 * |T|) and [2 * |T|, 3 * |T|) and so on.. by using hash. Total time is |S| * sqrt(|S|). After, do the same to second string. You will have a two arrays of divisors of each string (the array of hashes). Then, you calculate how many divisors are common.

That's all.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    amount of divisors is at maximum .

    ur wrong. aaaa has divisors (a, aa, and aaaa), but .

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

      yes you are correct. can you suggest how to solve this?

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

        Yes, he's wrong. there r no more 2 * sqrt(|S|) divisors. And, BTW, this problem can solved without using any string algorithm. See my solution. Sry for bad eng.

        → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Omg, authors solution is really strange. We can find all divisors of the string in O(n) using Z-algorithm or KMP. Hashing can be used to compare divisors, but it could be simply done in naive way in O(n) totally for all divisors.

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

    what do you mean by naive way? comparing all divisors char by char should be O(n^2), right?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Nope, it's not. 6729772

      There are not that many divisors for a given N. So in fact the complexity is something around O(n4 / 3)

      This discussion in Russian brings the estimate for cubic root: http://codeforces.net/blog/entry/651. You can google translate it or just read the links from it.

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
          vector<bool> is_div1(n), is_div2(m); // true if there is divisor with length i+1
    int ans=0;
    for(int i=0;i<min(n,m);i++)
    {
        if(a[i]!=b[i]) break;
        if(is_div1[i] && is_div2[i]) ans++;
    }

      All divisors are prefixes of the strings. So, we can check all common prefixes if they are divisors in both strings.

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hey i am solving it with hashing but i am getting WA. same code gives correct answer on IDEONE http://ideone.com/1cv777 http://codeforces.net/contest/182/submission/6734760

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

    someone please help me in debugging. i using lots of printfs but still i am unable to figure out the source of error. as i am yet to get AC on a hashing problem i dont feel very confident about it.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I have changed both

      for (int j = 0

      into

      for (int j = i

      and it passed first three tests :D

      → Reply