Skip to content

Instantly share code, notes, and snippets.

@rndD
Created March 3, 2015 17:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save rndD/005fa639c2b962a0e298 to your computer and use it in GitHub Desktop.
Save rndD/005fa639c2b962a0e298 to your computer and use it in GitHub Desktop.
Поиск подстроки внахлест
# -*- coding: utf-8 -*-
import re
def count_substrings_re(string, substring):
substring_re = '(?=(%s))' % re.escape(substring)
return len(re.findall(substring_re, string))
def count_substrings(s, f):
ind = 1
count = 0
while ind != -1:
ind = s.find(f)
if ind >= 0:
count += 1
s = s[ind+1:]
return count
if __name__ == '__main__':
import timeit
big_string = "avavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvava vavavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvavavavavrewwevavavewrewrew vavvavav";
print len(big_string)
print(timeit.timeit(
"count_substrings_re('%s', 'vav')" % big_string,
setup="from __main__ import count_substrings_re"
)
)
print(timeit.timeit(
"count_substrings('%s', 'vav')" % big_string,
setup="from __main__ import count_substrings"
)
)
# Выдает
#279
#20.2662341595
#26.177601099
@ReinRaus
Copy link

ReinRaus commented Mar 4, 2015

Добавил свой, немного оптимизированный вариант
https://gist.github.com/ReinRaus/8846dc49fc532d4e1b28

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment