3 ms·

I hate such stupid tricks, frankly a hash table or an array for a restricted domain is way faster, since the whole data structure gets cached on the L1. I can

by TARMAP 16y ago

I hate such stupid tricks, frankly a hash table or an array for a restricted domain is way faster, since the whole data structure gets cached on the L1. I can solve the same problem by using statistical thermodynamics, and show its only o(1), since each string is a configuration of the system and finding common alphabets is like finding degenerate states.

mdwrigh2 16y ago
How could you do this in O(1)? Or are you saying you can get a probably right answer in O(1)?
- swolchok 16y ago
  It's impossible to do in O(1) in the worst case, because you have to at least examine all the input (e.g., if the input matches the regex AA*B.)
  - mdwrigh2 16y ago
    That was my thought process, but the parent of my post claimed he could do it in O(1) (actually, he claimed it in o(1), but I'm assuming he just typo'd). Hence my question.
    - TARMAP 16y ago
      http://en.wikipedia.org/wiki/Chinese_room http://en.wikipedia.org/wiki/Chinese_room