CG_Naive.json

{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "t = 'haystack needle haystack' # \"text\" - thing we search in\n",
      "p = '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 i in xrange(0, len(t)-len(p)+1):  # for each alignment of p to t\n",
      "        match = True  # assume we match until proven wrong\n",
      "        for j in xrange(0, len(p)):  # for each position of p\n",
      "            if t[i+j] != p[j]:\n",
      "                match = False  # at least 1 char mismatches\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": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "[9]"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "t[9:9+len(p)]  # confirm it really occurs"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "'needle'"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "naive('needle', 'needleneedleneedle')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "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": {}
  }
 ]
}