Performant language/method to find a series of integers within an expansion of pi

Question

I am writing an interactive educational app that locates a series of integers, input by a user, in a million-digit expansion of pi. I am trying to decide upon an approach. Which programming language/method would be fastest?

Answer 1

It's just ordinary old substring search.

1. Store the precomputed digits in a string.
2. Use one of the linear-time substring search algorithms, like KMP, to search for the user-entered substring. Actually, the naive O(n^2) substring search (which is how C's strstr() is typically implemented) is probably fast enough if the user-entered string will be less than 100 digits or so, and will almost certainly be faster than any fancier algorithm for user-entered strings of less than 10 digits or so. (These numbers are educated guesses.)

These algorithms can be expressed in any language, but if you use an interpreted language like Python, try using whatever built-in string-searching function(s) (including regexes) it has before implementing KMP yourself -- built-in functions will be internally implemented in a compiled language, so should be a constant factor faster.