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