<jupyter_start><jupyter_text>0.3_ss_chap-2-3  最大共通文字列  Greedy<jupyter_code>from nltk.corpus import words
import random
import itertools
import logging
import numpy as np
logging.basicConfig(level=logging.DEBUG)
logger = logging.getLogger()
random.seed(0)
def random_word():
    return random.choice(words.words())
word = random_word()
word
compare = random_word()
compare
def forward_slice_word(word, n):
    ''' 前から n 文字を返す '''
    return word if n == 0 else word[0:-n]
for i in range(len(word)):
    substr = forward_slice_word(word, i)
substr<jupyter_output><empty_output><jupyter_text>先頭の文字も変えないとだ<jupyter_code>word[0:5]
word[0:10]
len(word)
def max_substr(word, compare):
    logger.debug(f"Which part of {word} is in {compare}?")
    max_len = 0
    max_part = ''
    for start, end in itertools.combinations(range(len(word)+1), 2):
        substr = word[start:end]
        if substr in compare: # ちゃんと書いたほうがいいかも
            if len(substr) > max_len:
                max_len = len(substr)
                max_part = substr
    logger.debug(f"Max part is {max_part}, length {max_len}")
    return max_len, max_part
for i in range(10):
    max_substr(random_word(), random_word())
n = len(word)
m = len(compare)
dp = np.zeros((n+1, m+1))
def max_substr_dp(word, compare):
    logger.debug(f"Which part of {word} is in {compare}?")
    
    n = len(word)
    m = len(compare)
    dp = np.zeros((n+1, m+1))
    answer = {}

    for i in range(n):
        for j in range(m):
            if word[i] == compare[j]:
                dp[i+1][j+1] = dp[i][j] + 1
                answer.update({i: word[i]})
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
                
    # assert dp[n][m] == len(answer)
    logger.debug(f"Max part is answer: {answer}, len: {len(answer)}, dp: {dp[n][m]}")
    return answer, dp
for i in range(10):
    max_substr_dp(random_word(), random_word())<jupyter_output>DEBUG:root:Which part of mailed is in antiquarianize?
DEBUG:root:Max part is answer: {1: 'a', 2: 'i', 4: 'e'}, len: 3, dp: 3.0
DEBUG:root:Which part of fadeless is in outwalk?
DEBUG:root:Max part is answer: {1: 'a', 4: 'l'}, len: 2, dp: 2.0
DEBUG:root:Which part of nonshaft is in levity?
DEBUG:root:Max part is answer: {7: 't'}, len: 1, dp: 1.0
DEBUG:root:Which part of tractarianize is in unhedge?
DEBUG:root:Max part is answer: {9: 'n', 12: 'e'}, len: 2, dp: 2.0
DEBUG:root:Which part of granulitize is in noise?
DEBUG:root:Max part is answer: {3: 'n', 6: 'i', 8: 'i', 10: 'e'}, len: 4, dp: 3.0
DEBUG:root:Which part of indusium is in precisianist?
DEBUG:root:Max part is answer: {0: 'i', 1: 'n', 4: 's', 5: 'i'}, len: 4, dp: 3.0
DEBUG:root:Which part of writhen is in douc?
DEBUG:root:Max part is answer: {}, len: 0, dp: 0.0
DEBUG:root:Which part of orogeny is in circuitman?
DEBUG:root:Max part is answer: {1: 'r', 5: 'n'}, len: 2, dp: 2.0
DEBUG:root:Which part of frozen is in circumnutate?
DEB[...]<jupyter_text>One loop<jupyter_code>for i in range(n):
    for j in range(W+1):
        if j < w[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(d[i][j], dp[i+1][j-w[i]]+v[i])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1635617303441743, 'fraction_numerical': 0.024628986422481843, 'mean_word_length': 3.5, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '342261', 'license': 'FTL', 'n_tokens_mistral': 1289, 'n_tokens_neox': 1245, 'n_words': 347, 'path': 'notebooks/0.3_ss_chap2-3.ipynb', 'repo_name': 'banbiossa/ant-book', 'size': '3167'}