Pattern Searching.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# KMP Algorithm\n",
    "Given a string **S** and a pattern **P**(also an string) then we have to find that if this string is in **S** or not <br>\n",
    "Brute Force : for every character in S we check that from there upto m(size of P) if the string is same as **P** or not if it is then we can return<br>\n",
    "Time Complexity : O(mn)<br>\n",
    "Algorithm: \n",
    "1. If there is no duplicate in P then wwhile matching if we have matched upto a certain length and then next character doesn't match then we shouldn't go to initial state + 1 as all matched are unique so we have to move only pointer of P string to start not S string\n",
    "2. Now if we have duplicates and we have matched a certain length of string and we encounter a character which is not matching then we will find among the matched string we will find a suffix which is equal to prefix i.e. ABAx form where x is unmatched character and A is suffix and prefix and B is some random string\n",
    "3. if there exist multiple suffix = prefix then we will take longest suffix possible so that we can go as much back as possible\n",
    "4. after finding suffix we can move P string pointer to next character of suffix and don't move S string pointer back i.e., move it one character forward and then again we start comparing\n",
    "5. We will use a suffix array (Pi array/ LPS array) to store maximum length of suffix\n",
    "6. if there is an overlap between suffix and prefix then also we will consider them eg. aaaa then at third index maxlength of suffix. = 3 prefix. = aaa suffix = aaa\n",
    "        Index    : 0 1 2 3 4 5 6 7 8 9 10 11 12 13\n",
    "        P String : A B A B X Y Z A B A  B  Y  Y  Z\n",
    "        LPS array: 0 0 1 2 0 0 0 1 2 3  4  0  0  0\n",
    "        \n",
    "        Let S string be A B A B X Y Z A B A B  A B X Y Z A B A B  Y  Y  Z\n",
    "        P pointer :     0 1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 11 12 13\n",
    "        problem at 11 index as S[11]!=P[11] and upto now it is equal so we will look at previous index and take \n",
    "        it's LPS array value i.e., 4 and move our P pointer to 4th index. Now at 4th index still value not equal\n",
    "        so LPS value of 3rd index i.e., 2 so put P pointer to index 2.\n",
    "        Now all will be equal and we will get to end of P string\n",
    "        If it wouln't have matched till 0th index then we will only move S pointer ahead\n",
    "To create LPS :\n",
    "1. we will use a current pointer and a prefix pointer and put first index of array as 0, prefix as 0 and current as 1\n",
    "2. Now if P[current] == P[prefix] then current++, Prefix++\n",
    "\n",
    "- **Time Complexity : O(m+n)** \n",
    "    - to run KMP O(n) and to create LPS array O(m)\n",
    "    - In similiar case to create a list/ hash of size n (when capacity is full then copy to other location and then insert 1 in O(1)\n",
    "    - as we are considering that at a stage P will fo back m index then in all previous m-1 stage O(1) time will take"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def CreateLPS(p):\n",
    "    prefix, current, n = 0, 1, len(p)\n",
    "    LPS = [0]*n\n",
    "    while current<n:\n",
    "        if p[current] == p[prefix]:\n",
    "            prefix +=1\n",
    "            LPS[current] = prefix\n",
    "            current+=1\n",
    "        else:\n",
    "            if prefix == 0:\n",
    "                LPS[current] = 0\n",
    "                current += 1\n",
    "            prefix = LPS[prefix-1]\n",
    "    return LPS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def KMP(s,p):\n",
    "    n,m = len(s), len(p)\n",
    "    LPS = CreateLPS(p)\n",
    "    i = j = 0\n",
    "    while(i<n):\n",
    "        if(s[i]==p[j]):\n",
    "            j+=1\n",
    "            i+=1\n",
    "            if j==m:\n",
    "                print(f'pattern found at {i-m}')\n",
    "                return True\n",
    "        else:\n",
    "            if j==0:\n",
    "                i+=1\n",
    "            else:\n",
    "                j = LPS[j-1]\n",
    "    print(\"Patten Not Found\")\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "pattern found at 9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "KMP(\"ABABXYZABABABXYZABABYYZ\",\"ABABXYZABABYYZ\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Rabin Karp\n",
    "Use concept of Rolling Hash\n",
    "Choose a prime no. n and calculate hash for pattern as p[0] + p[1]*n + p[2]*n^2 + p[3]*n^3 ....<br>\n",
    "now for checking in s string we use same for first m characters then if hash is not same then include next and remove last (hash - p[0])/p , hash+=p[m]*n^(m-1)\n",
    "<br> problem in storing big no. as hash"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}