title: Substring search algorithms (very large haystack, small needle)
body: <p>I know there are already several similar questions here, but I need some recommendations for my case (couldn't find anything similar).</p>
  
  <p>I have to search a very large amount of data for a substring that would be about a billion times smaller (10 bytes in 10 billion bytes). The haystack doesn't change, so I can bear with large precomputation if needed. I just need the searching part to be as fast as possible.</p>
  
  <p>I found algorithms which take <em>O(n)</em> time (<em>n</em> = haystack size, <em>m</em> = needle size), and the naive search takes <em>O(n+m)</em>. As the <em>m</em> in this particular case would be very small, is there any other algorithm I could look into?</p>
  
  <p>Edit:
  Thanks everyone for your suggestions!
  Some more info -
  The data could be considered random bits, so I don't think any kind of indexing / sorting would be possible. The data to be searched can be anything, not english words or anything predictable.</p>