{
 "metadata": {
  "name": "",
  "signature": "sha256:194023b80125d2c41b13f1b7450cf19d3f6acf84b77c8d9b52319995e5101873"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def suffixPrefixMatch(str1, str2, min_overlap):\n",
      "    ''' Returns length of longest suffix of str1 that is prefix of\n",
      "        str2, as long as that suffix is at least as long as min_overlap. '''\n",
      "    if len(str2) < min_overlap: return 0\n",
      "    str2_prefix = str2[:min_overlap]\n",
      "    str1_pos = -1\n",
      "    while True:\n",
      "        str1_pos = str1.find(str2_prefix, str1_pos + 1)\n",
      "        if str1_pos == -1: return 0\n",
      "        str1_suffix = str1[str1_pos:]\n",
      "        if str2.startswith(str1_suffix): return len(str1_suffix)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# overlap is 'more'\n",
      "suffixPrefixMatch('a little more', 'more than kin', min_overlap=3)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "4"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# len('more') < 5 so overlap won't be found\n",
      "suffixPrefixMatch('a little more', 'more than kin', min_overlap=5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "0"
       ]
      }
     ],
     "prompt_number": 3
    }
   ],
   "metadata": {}
  }
 ]
}