CG_SuffixTrie.json

{
 "metadata": {
  "name": "CG_SuffixTrie"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class SuffixTrie(object):\n",
      "    \n",
      "    def __init__(self, t):\n",
      "        \"\"\" Make suffix trie from t \"\"\"\n",
      "        t += '$' # special terminator symbol\n",
      "        self.root = {}\n",
      "        for i in xrange(len(t)): # for each suffix\n",
      "            cur = self.root\n",
      "            for c in t[i:]: # for each character in i'th suffix\n",
      "                if c not in cur:\n",
      "                    cur[c] = {} # add outgoing edge if necessary\n",
      "                cur = cur[c]\n",
      "    \n",
      "    def followPath(self, s):\n",
      "        \"\"\" Follow path given by characters of s.  Return node at\n",
      "            end of path, or None if we fall off. \"\"\"\n",
      "        cur = self.root\n",
      "        for c in s:\n",
      "            if c not in cur:\n",
      "                return None\n",
      "            cur = cur[c]\n",
      "        return cur\n",
      "    \n",
      "    def hasSubstring(self, s):\n",
      "        \"\"\" Return true iff s appears as a substring of t \"\"\"\n",
      "        return self.followPath(s) is not None\n",
      "    \n",
      "    def hasSuffix(self, s):\n",
      "        \"\"\" Return true iff s is a suffix of t \"\"\"\n",
      "        node = self.followPath(s)\n",
      "        return node is not None and '$' in node"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "strie = SuffixTrie('there would have been a time for such a word')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "strie.hasSubstring('nope')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "strie.hasSubstring('would have been')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "strie.hasSubstring('such a word')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "strie.hasSuffix('would have been')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "False"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "strie.hasSuffix('such a word')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "True"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    }
   ],
   "metadata": {}
  }
 ]
}