ALDS1_14の解答例(Python)

文字列の検索に関する問題です． アルゴリズムについて詳しく知りたい方は参考文献などをご覧ください． C,Dに関しては解き方がよく分からなかったので中途半端な解答になっています．

1. ALDS1_14_A: Naive String Search

# ALDS1_14_A
T = input()
P = input()

for i in range(len(T)-len(P)+1):
    if T[i:i+len(P)] == P:
        print(i)

2. ALDS1_14_B: String Search

# ALDS1_14_B
T = input()
P = input()

for i in range(len(T)-len(P)+1):
    if T[i:i+len(P)] == P:
        print(i)

3. ALDS1_14_C: Pattern Search

参考サイト

• BM法 BM法についてわかりやすく解説（C言語サンプル付き）
• ローリングハッシュ Rolling Hashのおはなし
• ラビン-カープ文字列検索アルゴリズム ラビン-カープ文字列検索アルゴリズム -Wikipedia

# 参考 https://daeudaeu.com/c-bm-search/#i-6
# ----------------------------ここから---------------------------------- #
def makeTable1(pattern, pattern_len):
    table1 = {}
    for pos in range(pattern_len):
        table1[pattern[pos]] = pattern_len - 1 - pos
    return table1

def makeTable2(pattern, pattern_len):
    table2 = [-1] * pattern_len

    for tail_pos in range(pattern_len - 1):
        eq_len = 0
        while eq_len < tail_pos and pattern[tail_pos - eq_len] == pattern[pattern_len - 1 - eq_len]:
            eq_len += 1

        if eq_len == 0:
            continue

        if pattern[tail_pos - eq_len] != pattern[pattern_len - 1 - eq_len]:
            table2[pattern_len - 1 - eq_len] = pattern_len - 1 - tail_pos + eq_len

    tail_pos = -1
    for pattern_pos in range(pattern_len - 2, -1, -1):
        eq_len = pattern_len - 1 - pattern_pos
        i = 0
        while i < eq_len and pattern[i] == pattern[pattern_pos + 1 + i]:
            i += 1

        if eq_len == i:
            tail_pos = eq_len - 1

        if table2[pattern_pos] == -1:
            if tail_pos != -1:
                table2[pattern_pos] = pattern_len - 1 - tail_pos + pattern_len - 1 - pattern_pos

    for pattern_pos in range(pattern_len - 2, -1, -1):
        if table2[pattern_pos] == -1:
            table2[pattern_pos] = pattern_len + (pattern_len - 1 - pattern_pos)

    return table2

def bmSearch(text, pattern,col):
    text_len = len(text)
    pattern_len = len(pattern)

    table1 = makeTable1(pattern, pattern_len)
    table2 = makeTable2(pattern, pattern_len)

    pattern_pos = pattern_len - 1
    text_pos = pattern_len - 1
    
    pos_list = []

    while text_pos < text_len:
        if text[text_pos] == pattern[pattern_pos]:
            if pattern_pos == 0:
                pos_list.append([text_pos,col])
                text_pos += len(pattern)
                pattern_pos = pattern_len - 1
                continue
            text_pos -= 1
            pattern_pos -= 1
        else:
            if text[text_pos] in table1.keys():
                t1 = table1[text[text_pos]]
            else:
                t1 = len(pattern)
                
            if t1 > table2[pattern_pos]:
                text_pos += t1
            else:
                text_pos += table2[pattern_pos]
            pattern_pos = pattern_len - 1

    return pos_list

# --------------------------------ここまで------------------------------------- #

H,W = map(int,input().split(" "))
str_set = set()
T = []
for _ in range(H):
    s = input()
    str_set = str_set | set(s)
    T.append(s)
    
R,C = map(int,input().split(" "))
P = []
str_set2 = set() # Pに含まれる文字の種類を把握する
for _ in range(R):
    s = input()
    str_set = str_set | set(s)
    str_set2 = str_set2 | set(s)
    P.append(s)
    
def get_value(row,start,end):
    return (rolling_hash[row][end]-rolling_hash[row][start]*num_dict[end-start]) % mod
    
# 1つの文字しか含まない極端な場合は別の処理をする
if len(set(str_set2))==1:
    # 1つの文字以外が含まれている場合 そこは一致しない
    key = list(str_set2)[0]
    ng_list = []
    for i in range(H):
        for j in range(W):
            if T[i][j] != key:
                for k in range(max(i+1-R,0),i+1):
                    for l in range(max(j+1-C,0),j+1):
                        ng_list.append(str(k)+","+str(l))

    ng_set = set(ng_list)
    for i in range(H-R+1):
        for j in range(W-C+1):
            if str(i)+","+str(j) not in ng_set:
                print(i,j)
                
else:
    inversed = False
    
    # 行と列を比較し，列の方が多ければ入れ替える
    if R<=C:
        pass
    else:
        T2 = ["" for i in range(W)]
        for t in T:
            for i in range(W):
                T2[i] += t[i]

        P2 = ["" for i in range(C)]
        for p in P:
            for i in range(C):
                P2[i] += p[i]

        H,W = W,H
        R,C = C,R
        T = T2
        P = P2
        inversed = True


    # ローリングハッシュ用の変数
    base_num = len(str_set)+1
    mod = 2**32-1
    num_dict = {i:(base_num**i)%mod for i in range(W+1)}
    str_dict = {s:i+1 for i,s in enumerate(str_set)} # ordの代わりに使う辞書

    # H×Wの文字列をローリングハッシュに
    rolling_hash = [[0 for _ in range(W+1)] for _ in range(H)]
    for i in range(H):
        hash_value = 0
        for j in range(W):
            num = num_dict[j]
            hash_value = str_dict[T[i][j]]
            rolling_hash[i][j+1] = (rolling_hash[i][j]*base_num + hash_value) % mod

    # R×Cの文字列ををハッシュ化
    hash_value0 = [0 for i in range(R)]
    for i in range(R):
        for j in range(C):
            hash_value0[i] += (str_dict[P[i][j]] * num_dict[C-j-1])

        hash_value0[i] = hash_value0[i] % mod

    # 各列のどこで一致するかをBM法で調べる
    result = []
    pattern = hash_value0
    for col in range(W-C+1):
        text =[get_value(row,col,col+C) for row in range(H)]
        result += bmSearch(text, pattern,col)

    # 答えを行が小さい順に並び替える
    if inversed:
        result.sort(key=lambda x:x[1])
    else:
        result.sort()

    for ans in result:
        if inversed:
            print(ans[1],ans[0])
        else:
            print(*ans)

4. ALDS1_14_D: Multiple String Matching

# ALDS1_14_D
from bisect import bisect_left
S = input()
n = int(input())

S_list = [S[i:1000+i] for i in range(len(S))]
S_list.sort() # 二分探索が使えるようにソートする

for _ in range(n):
    s = input() 
    idx = bisect_left(S_list,s) # 二分探索で文字列が含まれるかもしれない位置を調べる
    if idx == len(S_list):
        print(0)
    elif s not in S_list[idx]:
        print(0)
    else:
        print(1)