How can I make a faster search algorithm

[paul18fr]

your topic is quite challenging; I'm not a specialist but it piqued my interest

Find here after another code (among others ) to change "0" to "1" in your "big_Erdos1" list:

t0 = time.time()
big_Erdos1=list("01101001101101001001101001001101001101101011001101000101101001001111001001101001101100001101101011001101010001101001101101001101001000101101001101101001001101101001101001110101000011101001001110001101101001001110010101001011101101001001101001101101001001100111000111010001101001100101001011101001101101001101001001101001100101101010010101101001101001001101010110101011000101001111001000110101101001101001001101001111001000101111001001101101001101001001101001101101001101001001101101000011101001100111000101101001011000101101101001001100111101001001001111001001110001101101001100101001001101101001001011101101001001100101101101001001001101101001110001101001101100011100011011000011100101101001001101001101101011001100110000111011001100001101110011000111000010101101101101010000111001101001101101001001001101001101101001100101001010101111000101011001001010101101011100101001001011100101110001101001001101100110001101011001101000101101001011001101001101001011101001100101011100101001101101001001011000101101011001101001110100001100101101011001101001101011001101000101101001110000101011001101001101101101001001001111000110001010110101110010110010100101011000111011")
big_Erdos1 = np.asarray(big_Erdos1, dtype = int);
ones_ = np.where(big_Erdos1 == 1);
zeros_ = np.where(big_Erdos1 == 0);
big_Erdos1[ones_] = 0;
big_Erdos1[zeros_] = 1;
t1 = time.time()
print("Duration step 1 : ", t1-t0)

But I do not understand the second part; in your first post you said it's difficult to look for thousands of letters ; I played with the following code in order to look for a pattern of 100 000 numbers; I cannot avoid loops but it takes about 18 seconds to find 1 occurence I've created (it can probably improved).

P
from numba import jit
import numpy as np
import time, os, re

n = 100000;
vect3 = np.random.randint(2,size = 2*n);
vect4 = np.random.randint(2,size = n);
vect3[1506:1506+n] = vect4;

## initialization / No match by default
check = np.full(2*n, False, dtype = bool);

## partially vectorized
t0 = time.time()
for i in range(2*n):
    check[i] = np.array_equiv(vect3[i:n+i],vect4);


sol = np.where(check == True); ## we're lokking for True occurences
if (sol == []):
    print("No match")
else:
    l = np.size(sol);
    print("There are %d matche(s)" %l)

t1 = time.time()    
print("Duration method 1: ", t1-t0)


## using numba
t0 = time.time()
check2 = np.full(2*n, False, dtype = bool);

## function for Numba
#@jit(nopython=True, parallel = True) ## numpy.array_equiv seems not to be supproted :-(
@jit(parallel = True) 
def function_check(n, check2, vect3, vect4):         
    for i in range(2*n):
        check2[i] = np.array_equiv(vect3[i:n+i],vect4);       
    pass;



## function call
function_check(n, check2, vect3, vect4);

sol = np.where(check2 == True);
if (sol == []):
    print("No match")
else:
    l = np.size(sol);
    print("There are %d matche(s)" %l)

t1 = time.time()    
print("Duration method 2: ", t1-t0)

I do not master Numba enough to avoid the error