overlap_substrings.py

# -*- 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_re_opt(string, substring):
    if len( substring )==1:
        substring_re = re.escape( substring )
    else:
        substring_re = re.escape( substring[0] ) + "(?=" + re.escape( substring[1:] ) + ")"
    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"
              ),
              count_substrings_re( big_string, 'vav' )
         )
    print( timeit.timeit(
              "count_substrings_re_opt('%s', 'vav')" % big_string,
              setup="from __main__ import count_substrings_re_opt"
              ),
              count_substrings_re_opt( big_string, 'vav' )
         )
    print( timeit.timeit(
              "count_substrings('%s', 'vav')" % big_string,
              setup="from __main__ import count_substrings"
              ),
              count_substrings( big_string, 'vav' )
         )

# 280
# 26.21583244525716 61
# 19.634169350851955 61
# 40.01000176189752 61