Electro_Valkyrie's blog

How to make the constant factor of string hashing for substring matching lesser.
By Electro_Valkyrie, history, 9 months ago, In English

Please share your thoughts

-- Some tips which can help to reduce the constant factor of string match using hashing.

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

make your own hashing method, but it can't be less than O(len of string) for each key as you would need to iterate through each letter. I don't think this is what you wanted to know that is to avoid O(length) but I don't think it is possible

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

    I was asking for some type of optimisation we can do by some sort of precomputation or some optimised way of using hashing to check the match between two strings.I know we can't do better than O(n or nlogn) but i get TLE too many times using it even its complexity is not that much, But because of its high constant factor as computation needed for calculating hash is very much costly leading to high constant factor of time complexity.

    → Reply
    • »
      »
      »
      9 months ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      You can (but only if you get TLE) forget about the modulo. By storing all the values on unsigned long long, all the operations will be done modulo $$$2^{64}$$$. This will be a lot faster since % is generally very slow. On the other side you will have a bad modulo...

      → Reply