# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     name: python3
# ---

# + [markdown] id="view-in-github" colab_type="text"
# <a href="https://colab.research.google.com/github/NoCodeProgram/CodingTest/blob/main/dynamicProgramming/lgstCmnSubstr.ipynb" target="_parent"><img src="https://colab.research.google.com/assets/colab-badge.svg" alt="Open In Colab"/></a>

# + [markdown] id="a5ePZmPHhPY0"
# Title :  Longest Common Substring
#
# Chapter : Dynamic Programming
#
# Link : 
#
# ChapterLink : [PlayList](https://youtube.com/playlist?list=PLDV-cCQnUlIa0owhTLK-VT994Qh6XTy4v)
#
# 문제: text1과 text2의 longest common substring 과 그 길이를 구하여라

# + colab={"base_uri": "https://localhost:8080/"} id="l2xrebVAhNk2" outputId="92d824e3-b087-49ef-c3c0-595ede5b94b1"

def longestCommonSubstr(text1:str, text2:str):
  dp_table = [[0]*(len(text1)+1) for j in range(len(text2)+1)]

  max_dp = -1
  max_loc = [-1,-1]

  for rowIdx in range(1,len(dp_table)):
    prev_row = rowIdx - 1
    char2 = text2[rowIdx-1]
    for colIdx in range(1,len(dp_table[rowIdx])):
      prev_col = colIdx-1
      char1 = text1[colIdx-1]
      
      dp = 0
      if char1 == char2:
        dp = dp_table[prev_row][prev_col] + 1
      else:
        dp = 0
      
      if max_dp < dp:
        max_dp = dp
        max_loc = [rowIdx,colIdx]              
      dp_table[rowIdx][colIdx] = dp

  lcs_length = max_dp
  lcs_end = max_loc[0] #text2, rowIdx of dptable
  lcs_begin = lcs_end-lcs_length
  lcs = text2[lcs_begin:lcs_end]

  return (lcs_length,lcs)
 

text1 = 'yeshowmuchiloveyoumydearmotherreallyicannotbelieveit'
text2 = 'yeaphowmuchiloveyoumydearmother'
print(longestCommonSubstr(text1,text2))


# + id="Lpxjsp5qhgB_"


StarcoderdataJupyterScriptsDedupFiltered