ForHosting KIT · 文章作成・要約AI

最長共通部分列計算機

Q: LCSは最長共通部分文字列と同じですか？

いいえ。 部分文字列は連続である必要がありますが、部分列は文字を飛ばせます。本計算機は古典的動的計画法で部分列問題を解きます。

2つの文字列が同じ順序で共有する最も長い文字の並びを、間が空いていても見つけます。ABCBDABとBDCABAは長さ4を共有し、たとえばBCBAです。長さと、目で確かめられる有効な部分列が返ります。ブラウザで無料で使えます。

無料
ブラウザで動作
登録不要
データは端末の外に出ません

無料で実行 API仕様を見る

ご利用方法ウェブAPIメールTelegramアプリ近日

計算例

入力した場合

文字列A: ABCBDAB
文字列B: BDCABA

結果

Len a: 7
Len b: 6
長さ: 4
部分列: BCBA

最長共通部分列問題は、必ずしも連続でなくてもよい、2つの入力文字列の中で同じ順序に現れる最長の文字列を求めます。行単位のdiffツール、バージョン管理のマージ支援、並べ替えノイズを許容する盗用検出、挿入・削除が完全な部分文字列一致より重要な生物学的配列比較の背後にある動的計画法の基盤です。この最長共通部分列計算機は2つの文字列を受け取り、長さの積に対して線形な時間で古典的な長さ表を埋め、バックトラックで有効なLCSを1つ再構成し、数値の長さと部分列文字列の両方を返します。空入力は有効で長さは0になります。

最長共通部分列とは何か（何でないか）

文字列の部分列とは、残った文字の順序を変えずに0個以上の文字を削除して得られる任意の文字列です。2文字列の共通部分列とは、両方の部分列になっている文字列です。最長共通部分列、すなわちLCSは、すべての共通部分列の中で長さが最大の共通部分列です。

最長共通部分文字列と異なり、LCSはどちらの入力でも連続ブロックを占める必要はありません。古典的な組ABCBDABとBDCABAは、再構成がどの同点を選ぶかに応じて、BCBAやBDABなど長さ4のLCS文字列を複数許します。

diffアルゴリズムとDNAアラインメントツールがこの非連続の概念を重視するのは、実際の編集が固定窓をずらすだけでなく記号の挿入・削除を行うからです。LCSの長さは有用な類似度スコアであり、再構成された文字はスコアの横に明示的なアラインメント骨格を示したいときに役立ちます。すべての可能なLCS、編集スクリプト、類似度パーセントは返しません。

それらは同じDP表の考えの上に立つ別問題です。

最長共通部分列が役立つ場面

コンピュータサイエンスの授業とオンラインジャッジは、学生がフルIDEに解答を貼り付けなくても、任意の短い文字列に対して正しい長さと有効な部分列を返す参照オラクルを必要とします。diffに近い製品機能—変更要約、マージ競合のヒント、ログ行の整列—は、より重い編集距離パスの前に安い類似信号としてLCS長を欲しがることが多いです。

バイオインフォマティクスの教材デモは玩具のDNAアルファベット文字列（A、C、G、T）を使い、挿入と削除があっても長い共有骨格が残ることを示します。文字列を長さ上限内に保ち、等長の複数答えのどれかが重要なら再構成部分列をテストに固定すれば、独自の数値ライブラリなしで再現可能なLCS結果が得られます。

活用例

アルゴリズム課題と講義デモ

学生に短い2文字列を与え、LCSの長さと返された部分列が各入力で本当に順序どおり現れるかを検証します。

LMSとコンテストの自動採点

不正入力を拒否し、古典的な表が許すより長い部分列を決して捏造しない決定的オラクルでDP課題を採点します。

diffと配列類似度の事前チェック

より重い編集距離やアラインメントパイプラインの前に、2テキストや玩具DNA文字列の共有された順序構造を採点します。

よくある質問

LCSは最長共通部分文字列と同じですか？

いいえ。部分文字列は連続である必要がありますが、部分列は文字を飛ばせます。本計算機は古典的動的計画法で部分列問題を解きます。

長さ制限と空文字列の規則は？

各文字列は最大500文字です。空文字列は許可され、length 0と空の部分列になります。

最長共通部分列が複数あるのはなぜですか？

同じ長さの候補がよくあるためです。ABCBDABとBDCABAには、BCBAやBDABなど長さ4のものが複数あります。ツールはそのうち1つを毎回同じ決め方で返すので、同じ組み合わせなら答えは変わりません。

LCSの長さは何に使えますか？

手軽な類似度の目安になります。変更の要約、統合の手がかり、ログ行のそろえ方などで、重い編集距離の計算の前に使えます。DNAの文字を使った授業の例にも向いています。

返された部分列が正しいかはどう確かめますか？

その文字が両方の文字列に同じ順序で現れるかを、ほかの文字は飛ばしてよいとして確かめ、長さが示された数と一致するかを見ます。BCBAはABCBDABとBDCABAの両方で成り立ちます。

開発者向け — APIアクセス

このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。

エンドポイント

POSThttps://api.kit.forhosting.com/dev/longest-common-subsequence

Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。

お使いのスタックから呼び出す

curl -X POST https://api.kit.forhosting.com/dev/longest-common-subsequence \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"string_a":"ABCBDAB","string_b":"BDCABA"}'

const res = await fetch("https://api.kit.forhosting.com/dev/longest-common-subsequence", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "string_a": "ABCBDAB",
    "string_b": "BDCABA"
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/dev/longest-common-subsequence",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "string_a": "ABCBDAB",
    "string_b": "BDCABA"
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/longest-common-subsequence", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"string_a":"ABCBDAB","string_b":"BDCABA"}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"string_a":"ABCBDAB","string_b":"BDCABA"}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/longest-common-subsequence", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

リクエスト例

{
  "string_a": "ABCBDAB",
  "string_b": "BDCABA"
}

レスポンス例

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "dev.longest_common_subsequence",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。

料金

1リクエストあたり$0.002

単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。

エラー

HTTP	コード	意味
`401`	`unauthorized`	APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。
`402`	`insufficient_balance`	残高が不足しています。チャージ後に再度お試しください。
`404`	`unknown_type`	指定されたタスクタイプは存在しません。タイプ名を確認してください。
`429`	`rate_limited`	リクエストが多すぎます。しばらく待ってから再度お試しください。

技術的な注記

最長共通部分列とは何か（何でないか）

このエンドポイントは両方を返します。

入力契約、アルゴリズム、応答形、制限

内部ではソルバが(m+1)×(n+1)の整数表を確保し、接頭辞が末尾文字で一致すればdp[i][j]をdp[i-1][j-1]+1、そうでなければ上と左の最大に設定し、右下から辿ります。ここで用いる素朴な表形式では時間・記憶ともO(m·n)です。必須の文字列フィールドstring_aとstring_bを含むJSON本体をPOSTしてください（別名a、s1、first、text_aおよびb、s2、second、text_bを受け付けます）。どちらも空で構いませんが、どちらも真のJSON文字列でなければならず、数値や配列は不可です。欠落フィールド、非文字列型、長すぎる入力はinvalid_inputで失敗し課金されません。成功時本体はstring_aとstring_bを返し、len_aとlen_bを報告し、length（LCS長）とsubsequence（1つのLCS文字列、空もあり）を含みます。一致ペアはその文字を追加して斜めに進み、同点では上へ（string_aから落とす）を優先し、再構成結果がランタイム間で安定します。

LCS APIが価値を生む場面

LMSの自動採点は固定ペアでAPIを呼び、長さと返された部分列が各入力の部分列であることを検証し、空や1文字の端でのみ落ちる表のオフバイワンを捕まえられます。実装は純粋parseのティアAのため、成功した各呼び出しはモデルトークンも外向きネットワークもなく公開の基本価格$0.002です。

技術的な質問

2文字列の最長共通部分列はどう計算しますか？

string_aとstring_bをJSON文字列で送ってください。APIはlength（LCS長）とsubsequence（1つの最大共通部分列）、入力のエコーと各長さを返します。

複数のLCSがあるときどれが返りますか？

最大長のLCSならどれでも正しいです。本実装は固定バックトラック（同点ではstring_aを落とす優先）を使い、同じ入力は常に同じ部分列文字列になります。

最長共通部分列計算機の料金は？

ブラウザツールは無料です。APIリクエストは成功呼び出しごとに$0.002の前払いKIT残高を使い、不正入力は課金されません。

KITの完全なドキュメントを見る →

最長共通部分列計算機

無料で実行

計算例

最長共通部分列とは何か（何でないか）

最長共通部分列が役立つ場面

活用例

アルゴリズム課題と講義デモ

LMSとコンテストの自動採点

diffと配列類似度の事前チェック

よくある質問

関連ツール

開発者向け — APIアクセス

エンドポイント

お使いのスタックから呼び出す

リクエスト例

レスポンス例

料金

エラー

技術的な注記

最長共通部分列とは何か（何でないか）

入力契約、アルゴリズム、応答形、制限

LCS APIが価値を生む場面

技術的な質問

ありがとう