Python runtime if substring in string

Question

What is Big O next if statement?

if "pl" in "apple":
   ...

What is the total O value of how python determines if the string "pl" is found in the string "apple"

or any other substring in a string search.

Is this the most efficient way to check if there is a substring in a string? Does it use the same algorithm as .find()?

Answer 1

In python 3.4.2 it looks like they are resorting to the same function, but, nevertheless, there may be a time difference. For example, you s.findmust first search for a method findfor a string, etc.

- Boyer-More Horspool.

Answer 2

O (N), O (NM) (N - , M - , ).

str.index(), str.find(), str.__contains__() ( in) str.replace(); - , -- .

fastsearch.h, fastsearch.h; Python 2.5 ( ).

Python- :

def find(s, p):
    # find first occurrence of p in s
    n = len(s)
    m = len(p)
    skip = delta1(p)[p[m-1]]
    i = 0
    while i <= n-m:
        if s[i+m-1] == p[m-1]: # (boyer-moore)
            # potential match
            if s[i:i+m-1] == p[:m-1]:
                return i
            if s[i+m] not in p:
                i = i + m + 1 # (sunday)
            else:
                i = i + skip # (horspool)
        else:
            # skip
            if s[i+m] not in p:
                i = i + m + 1 # (sunday)
            else:
                i = i + 1
    return -1 # not found

.

Answer 3

timeit :

maroun@DQHCPY1:~$ python -m timeit  = "apple";s.find("pl")'
10000000 loops, best of 3: 0.125 usec per loop
maroun@DQHCPY1:~$ python -m timeit  = "apple";"pl" in s'
10000000 loops, best of 3: 0.0371 usec per loop

in (0.0371 usec 0.125 usec).

.

Answer 4

I think the best way to find out is to look at the source. It looks like this __contains__::

static int
bytes_contains(PyObject *self, PyObject *arg)
{
    Py_ssize_t ival = PyNumber_AsSsize_t(arg, PyExc_ValueError);
    if (ival == -1 && PyErr_Occurred()) {
        Py_buffer varg;
        Py_ssize_t pos;
        PyErr_Clear();
        if (PyObject_GetBuffer(arg, &varg, PyBUF_SIMPLE) != 0)
            return -1;
        pos = stringlib_find(PyBytes_AS_STRING(self), Py_SIZE(self),
                             varg.buf, varg.len, 0);
        PyBuffer_Release(&varg);
        return pos >= 0;
    }
    if (ival < 0 || ival >= 256) {
        PyErr_SetString(PyExc_ValueError, "byte must be in range(0, 256)");
        return -1;
    }

    return memchr(PyBytes_AS_STRING(self), (int) ival, Py_SIZE(self)) != NULL;
}

in terms stringlib_find()in which it is used fastsearch().