文字列の配列に対して、各文字列の前方の共通部分（のみ）を抜き出すという例です。
Python等であれば、標準ライブラリなどにそのものズバリのものがありそうなという気もしましたが、ぱっと見見つけられませんでしたので、自作しました。 （この程度のものもスクラッチでさらさら書ける腕前ではなかったので、せっかくなので自分メモとして残しておきます。）
特別なことはやっていません。
(1) Python版
hoge.py
from functools import reduce from typing import * def common_prefix(str_list: List[str]) -> str: def common(a: str, b: str) -> str: idx = 0 for i, j, _ in zip(a, b, range(len(a))): if i != j: break idx = _ + 1 return a[:idx] return ''.join(reduce(common, str_list))
上記の確認用コード
ptns = [
['abcd', 'abc1234', 'abczf'],
['abc1234', 'abcd', 'abzf'],
['fbcd', 'abc1234', 'abczf'],
['abcd'],
['同じです', '同じです', '同じなら', '同じかな', '同じと思われる'],
['同じab', '同じxb', '同じby'], # //途中を挟んで微妙に一致するが、前方部分のみ検出すべき例
['同じbbz', '同じxbz', '同じbz'], # //途中を挟んで微妙に一致するが、前方部分のみ検出すべき例
['', '同じbbz', '', '同じxbz', '同じbz'] # //途中を挟んで微妙に一致するが、前方部分のみ検出すべき例
]
for idx, i in enumerate(ptns):
print(idx, i, "前方共通部分=", common_prefix(i))
↓ 実行結果
0 ['abcd', 'abc1234', 'abczf'] 前方共通部分= abc
1 ['abc1234', 'abcd', 'abzf'] 前方共通部分= ab
2 ['fbcd', 'abc1234', 'abczf'] 前方共通部分=
3 ['abcd'] 前方共通部分= abcd
4 ['同じです', '同じです', '同じなら', '同じかな', '同じと思われる'] 前方共通部分= 同じ
5 ['同じab', '同じxb', '同じby'] 前方共通部分= 同じ
6 ['同じbbz', '同じxbz', '同じbz'] 前方共通部分= 同じ
7 ['', '同じbbz', '', '同じxbz', '同じbz'] 前方共通部分=
アルゴリズムを差し替えられるようにする
from functools import reduce from typing import * def commonfunc(a: str, b: str) -> str: idx = 0 for i, j, _ in zip(a, b, range(len(a))): if i != j: break idx = _ + 1 return a[:idx] def common_prefix2(str_list: List[str], func) -> str: return ''.join(reduce(func, str_list)) for idx, i in enumerate(ptns): print(idx, i, "前方共通部分=", common_prefix2(i, commonfunc)) # 共通の文字の集合を取得(common_prefix2という名前からは合わなくなるケド...) def intersectfunc(a, b): return list(set(a) & set(b)) print('intersect版=', common_prefix2(['abcd', 'abc1234', 'abczf'], intersectfunc))
↓ 実行結果
0 ['abcd', 'abc1234', 'abczf'] 前方共通部分= abc 1 ['abc1234', 'abcd', 'abzf'] 前方共通部分= ab 2 ['fbcd', 'abc1234', 'abczf'] 前方共通部分= 3 ['abcd'] 前方共通部分= abcd 4 ['同じです', '同じです', '同じなら', '同じかな', '同じと思われる'] 前方共通部分= 同じ 5 ['同じab', '同じxb', '同じby'] 前方共通部分= 同じ 6 ['同じbbz', '同じxbz', '同じbz'] 前方共通部分= 同じ 7 ['', '同じbbz', '', '同じxbz', '同じbz'] 前方共通部分= intersect版= bac
SequenceMather版
ここで、ふと、difflibのSequenceMatherを思い出した（もともとうろ覚えだったので確かめながらだが...）。
...ので、そちらを活用してみる。
from functools import reduce from typing import * from difflib import SequenceMatcher def common_prefix2(str_list: List[str], func) -> str: return ''.join(reduce(func, str_list)) def commonfuncB(a, b): [(i, j, n), *_] = SequenceMatcher( None, a, b).get_matching_blocks() return a[:n] if (i == 0 and n > 0) else "" for idx, i in enumerate(ptns): print(idx, i, "前方共通部分=", common_prefix2(i, commonfuncB))
↓
当初の自作版と同じ結果が得られた。
(2) JavaScript版
試作品1
function common_prefix(strArray) {
const common = (a, b) => {
let idx = 0;
for (let i = 0; i < a.length; i++) {
if (a[i] !== b[i]) {
break;
}
idx = i + 1;
}
return a.slice(0, idx);
}
return strArray.map((a) => [...a]).reduce(
(acm, cur) => common(acm, cur)
).join('');
}
配列にした方が集合系の標準関数などが使えて良いかなと思ったので、"abcd" -> ["a","b","c","d"]とバラしたのですが、それらしき関数を探しきれず、結局、ちまちまループを回して可読性が高くないような気がするのと、また言うほど早いわけではなさそう。
ということで、startsWithとともに添字を含むロジックを無くして、仕様の意図がわかりやすく、ステップ数も少なそうな次のロジックに落ち着いております。
↓（試作品2)
試作品2
function common_prefix(strArray) {
return strArray.reduce(
(a, b) => {
let wrk = a
while (true) {
if (wrk.length == 0 || b.startsWith(wrk)) {
return wrk
}
wrk = wrk.slice(0, -1)
}
}
)
}
試作品3(2020/12/29)
このレベル＆要件（ひとまず動けばよい）であれば、もっと単純にできるかも。
function common(a, b) {
return (a.length == 0 || b.startsWith(a)) ? a : common(a.slice(0, -1), b);
}
['abc', 'abcd', 'abc1234', 'abczf'].reduce(common);
