CG_002_NaiveMatching1.json

{
 "metadata": {
  "name": "CG_002_NaiveMatching1"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "t = 'haystack needle haystack' # \"text\" - thing we search in\np = 'needle' # \"pattern\" - thing we search for",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "def naive(p, t):\n    assert len(p) <= len(t) # assume text at least as long as pattern\n    occurrences = []\n    # For each alignment of p to t\n    for i in xrange(0, len(t)-len(p)+1):\n        match = True # assume the pattern matches until proven wrong\n        # For each position of p\n        for j in xrange(0, len(p)):\n            if t[i+j] != p[j]:\n                match = False # at least 1 char mismatches, so no match\n                break\n        if match:\n            occurrences.append(i)\n    return occurrences",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "naive(p, t)",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 3,
       "text": "[9]"
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "t[9:9+len(p)] # let's confirm it really occurs",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "text": "'needle'"
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "naive('needle', 'needleneedleneedle')",
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 5,
       "text": "[0, 6, 12]"
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": "",
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    }
   ],
   "metadata": {}
  }
 ]
}