I’m trying to find a substring in an infinite sequence of numbers (Similar to Substring in a infinite sequence of numbers) and am a little stuck on improving my algorithm. I know there is already an answer given in the question I linked above, but I want to try and improve my brute force algorithm.

Given a sequence $ S = \{12345678910…n-1n | S \in \mathbb{Z}:\}$ , the algorithm tries to compute the first index of a pattern $ P$ in the string. For instance, $ \mathrm{find}(P = 456) == 3$ as the sequence $ 456$ is located at index $ 3$ . I have a very simple algorithm that generates a sequence till the substring is found, and then goes through the sequence to return the index of the substring. This algorithm is very slow for for large $ N$ and I want to improve it:

`def find_position(string): # Build a window of size len(string) and init from 1 -> m windowSize = len(string) window = [str(i) for i in range(1, windowSize + 1)] result = ''.join(window) # Loop till match while string not in result: # Remove front and add back window.append(str(int(window[-1]) + 1)) # Join window and match result = ''.join(window) return result.index(string) `

This algorithm is like a very basic Rabin-Karp without any hashing but just regular string matching. I am not too sure if adding a rolling hash would speed up this algorithm in any way because the slow aspect of the algorithm is generating and appending to the sequence and then checking if the string is contained in the window.

Any ideas on how to improve this algorithm?