Created
October 21, 2013 19:56
-
-
Save BenLangmead/7089885 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"metadata": { | |
"name": "" | |
}, | |
"nbformat": 3, | |
"nbformat_minor": 0, | |
"worksheets": [ | |
{ | |
"cells": [ | |
{ | |
"cell_type": "code", | |
"collapsed": false, | |
"input": [ | |
"import string\n", | |
"\n", | |
"def suffixPrefixMatch(x, y, k):\n", | |
" ''' Return length of longest suffix of x of length at least k that\n", | |
" matches a prefix of y. Return 0 if there no suffix/prefix\n", | |
" match has length at least k. '''\n", | |
" if len(x) < k or len(y) < k:\n", | |
" return 0\n", | |
" idx = len(y) # start at the right end of y\n", | |
" # Search right-to-left in y for length-k suffix of x\n", | |
" while True:\n", | |
" hit = string.rfind(y, x[-k:], 0, idx)\n", | |
" if hit == -1: # not found\n", | |
" return 0\n", | |
" ln = hit + k\n", | |
" # See if match can be extended to include entire prefix of y\n", | |
" if x[-ln:] == y[:ln]:\n", | |
" return ln # return length of prefix\n", | |
" idx = hit + k - 1 # keep searching to left in Y\n", | |
" return -1" | |
], | |
"language": "python", | |
"metadata": {}, | |
"outputs": [], | |
"prompt_number": 9 | |
}, | |
{ | |
"cell_type": "code", | |
"collapsed": false, | |
"input": [ | |
"# overlap is 'more'\n", | |
"suffixPrefixMatch('a little more', 'more than kin', k=3)" | |
], | |
"language": "python", | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"metadata": {}, | |
"output_type": "pyout", | |
"prompt_number": 12, | |
"text": [ | |
"4" | |
] | |
} | |
], | |
"prompt_number": 12 | |
}, | |
{ | |
"cell_type": "code", | |
"collapsed": false, | |
"input": [ | |
"# len('more') < 5 so overlap won't be found\n", | |
"suffixPrefixMatch('a little more', 'more than kin', k=5)" | |
], | |
"language": "python", | |
"metadata": {}, | |
"outputs": [ | |
{ | |
"metadata": {}, | |
"output_type": "pyout", | |
"prompt_number": 13, | |
"text": [ | |
"0" | |
] | |
} | |
], | |
"prompt_number": 13 | |
}, | |
{ | |
"cell_type": "code", | |
"collapsed": false, | |
"input": [], | |
"language": "python", | |
"metadata": {}, | |
"outputs": [] | |
} | |
], | |
"metadata": {} | |
} | |
] | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
thank you for your code but I have query about rfind function what will it return or what is the source code for it