Counting all permutations of a substring

Azolex cretin at des.alpes.ch
Thu Apr 6 10:03:57 EDT 2006


I wrote:
> [counting all (possibly overlapping) occurences of a substring in a string]
> 
> def count_subs(s,subs,pos=0) :
>     pos = 1+s.find(subs,pos)
>     return pos and 1+count_subs(s,subs,pos)                                                            .

now to push lisp-style to the extreme, a recursive one-liner solution 
with presumably better stack behavior (assuming proper tail-recursion 
elimination, which I doubt is the case in Python).

Python 2.5a1 (r25a1:43589, Apr  5 2006, 10:36:43) [MSC v.1310 32 bit 
(Intel)] on win32
...
>>> cnt_ss = lambda s,ss,p=-1,n=-1 : n if n>p else cnt_ss(s,ss,s.find(ss,p+1),n+1)
>>> cnt_ss("AABBAAABABAAA","AA")
5
>>> cnt_ss("foolish","bar")
0
>>> cnt_ss("banana split","ana")
2

note though that the first solution beats this one on token count: 37 vs 42



More information about the Python-list mailing list