Boyer-Moor Method.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "1caaae6b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3번째 문자가 일치\n"
     ]
    }
   ],
   "source": [
    "def bm_match(txt, pat):\n",
    "    skip = [None] * 256 # 건너뛰기 표(256은 ASCII 문자 집합의 크기)\n",
    "    \n",
    "    # 건너뛰기 표 만들기\n",
    "    for pt in range(256): # 0~255번 인덱스의 요소를 패턴의 길이로 초기화한다.\n",
    "        skip[pt] = len(pat)\n",
    "    for pt in range(len(pat)): # 패턴의 길이만큼 반복\n",
    "        skip[ord(pat[pt])] = len(pat) - pt - 1\n",
    "        # 건너뛰기 표에서 패턴 내의 현재 위치 (pt)를 해당 문자와 비교하여, 패턴의 길이에서 해당 값을 빼고 1을 뺀 값을 저장한다.\n",
    "    \n",
    "    # 검색하기\n",
    "    while pt < len(txt): # 텍스트의 위치를 가리키는 변수인 pt가 텍스트의 길이보다 작다면 while문 반복\n",
    "        pp = len(pat) - 1 # 패턴의 마지막 인덱스로 초기화\n",
    "        while txt[pt] == pat[pp]: # 텍스트와 패턴의 현재 위치에 있는 문자가 일치할 때까지 while문 반복\n",
    "            if pp == 0: # 패턴의 첫 번째 문자까지 일치하는 경우\n",
    "                return pt # 일치하는 위치 반환\n",
    "            pt -= 1 # 텍스트의 위치를 한 칸 앞으로 이동\n",
    "            pp -= 1 # 패턴의 위치를 한 칸 앞으로 이동\n",
    "        pt += skip[ord(txt[pt])] if skip[ord(txt[pt])] > len(pat) - pp \\\n",
    "        else len(pat) - pp\n",
    "        # 텍스트의 현재 위치에 대응하는 스킵 테이블 값을 사용하여 이동할 거리 결정\n",
    "        # 만약 건너뛰기 표의 값이 패턴의 길이에서 pp를 뺀 값보다 크다면, 해당 건너뛰기 표의 값 만큼 이동\n",
    "        # 그렇지 않으면, 패턴의 길이에서 pp를 뺀 값만큼 이동\n",
    "\n",
    "    return -1 # 검색실패 시 -1 반환\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    text = 'ABABCDEFGHA'\n",
    "    pattern = 'ABC'\n",
    "    \n",
    "    idx = bm_match(text, pattern)\n",
    "    print('텍스트 안에 패턴이 존재하지 않음') if idx == -1 else print(f'{(idx + 1)}번째 문자가 일치')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "dff25bdc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6번째 문자가 일치\n"
     ]
    }
   ],
   "source": [
    "def bm_match(txt, pat):\n",
    "    skip = [None] * 256 # 건너뛰기 표(256은 ASCII 문자 집합의 크기)\n",
    "    \n",
    "    # 건너뛰기 표 만들기\n",
    "    for pt in range(256): # 0~255번 인덱스의 요소를 패턴의 길이로 초기화한다.\n",
    "        skip[pt] = len(pat)\n",
    "    for pt in range(len(pat)): # 패턴의 길이만큼 반복\n",
    "        skip[ord(pat[pt])] = len(pat) - pt - 1\n",
    "        # 건너뛰기 표에서 패턴 내의 현재 위치 (pt)를 해당 문자와 비교하여, 패턴의 길이에서 해당 값을 빼고 1을 뺀 값을 저장한다.\n",
    "    # 검색하기\n",
    "    while pt < len(txt): # 텍스트의 위치를 가리키는 변수인 pt가 텍스트의 길이보다 작다면 while문 반복\n",
    "        pp = len(pat) - 1 # 패턴의 마지막 인덱스로 초기화\n",
    "        while txt[pt] == pat[pp]: # 텍스트와 패턴의 현재 위치에 있는 문자가 일치할 때까지 while문 반복\n",
    "            if pp == 0: # 패턴의 첫 번째 문자까지 일치하는 경우\n",
    "                return pt # 일치하는 위치 반환\n",
    "            pt -= 1 # 텍스트의 위치를 한 칸 앞으로 이동\n",
    "            pp -= 1 # 패턴의 위치를 한 칸 앞으로 이동\n",
    "        pt += skip[ord(txt[pt])] if skip[ord(txt[pt])] > len(pat) - pp \\\n",
    "        else len(pat) - pp\n",
    "        # 텍스트의 현재 위치에 대응하는 스킵 테이블 값을 사용하여 이동할 거리 결정\n",
    "        # 만약 건너뛰기 표의 값이 패턴의 길이에서 pp를 뺀 값보다 크다면, 해당 건너뛰기 표의 값 만큼 이동\n",
    "        # 그렇지 않으면, 패턴의 길이에서 pp를 뺀 값만큼 이동\n",
    "\n",
    "    return -1 # 검색실패 시 -1 반환\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    text = 'CGTGCCTACTTACTTA'\n",
    "    pattern = 'CTACT'\n",
    "    \n",
    "    idx = bm_match(text, pattern)\n",
    "    print('텍스트 안에 패턴이 존재하지 않음') if idx == -1 else print(f'{(idx + 1)}번째 문자가 일치')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "35796466",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}