حاسبة أطول تتابع مشترك
اعثر على أطول سلسلة أحرف يتشاركها نصان بالترتيب نفسه ولو بوجود فجوات: يتشارك ABCBDAB وBDCABA تتابعًا طوله 4، مثل BCBA. وتحصل على الطول وعلى تتابع صحيح يمكنك التحقق منه بعينك. مجاني في متصفحك.
- مجاني
- يعمل في متصفحك
- دون تسجيل
- بياناتك لا تغادر جهازك
شغّل الأداة مجانًا
مثال محلول
- السلسلة A
- ABCBDAB
- السلسلة B
- BDCABA
- Len a
- 7
- Len b
- 6
- الطول
- 4
- المتتالية الجزئية
- BCBA
تطلب مسألة أطول تتابع مشترك أطول سلسلة من المحارف التي تظهر بالترتيب نفسه داخل سلسلتي إدخال، دون اشتراط التجاور. وهي أساس البرمجة الديناميكية لأدوات diff السطرية، ومساعدات الدمج في أنظمة التحكم بالإصدارات، وكاشفات الانتحال التي تتحمل إعادة الترتيب الضوضائية، ومقارنة التسلسلات الحيوية حين تهم الإدراجات والحذوفات أكثر من تطابق السلسلة الفرعية التام. تقبل حاسبة أطول تتابع مشترك هذه سلسلتين، وتملأ جدول أطوال كلاسيكيًا بزمن خطي بالنسبة لجداء الطولين، وتعيد بناء LCS صالحًا بالرجوع للخلف، وتعيد الطول العددي وسلسلة التتابع معًا. المدخلات الفارغة صالحة وتعطي طولًا صفرًا.
ما هو أطول تتابع مشترك (وما ليس هو)
التتابع لسلسلة هو أي سلسلة تُحصل بحذف صفر أو أكثر من المحارف دون إعادة ترتيب الباقي. التتابع المشترك لسلسلتين هو سلسلة تكون تتابعًا لكلتيهما. أطول تتابع مشترك، أو LCS، هو أي تتابع مشترك يبلغ طوله الحد الأقصى بين كل التتابعات المشتركة.
بخلاف أطول سلسلة فرعية مشتركة، لا يلزم أن يشغل LCS كتلة متجاورة في أي من المدخلين: الزوج الكلاسيكي ABCBDAB وBDCABA يسمح بعدة سلاسل LCS بطول أربعة مثل BCBA وBDAB بحسب أي التعادلات تختارها إعادة البناء. تعتمد خوارزميات diff وأدوات محاذاة DNA على هذا المفهوم غير المتجاور لأن التعديلات الحقيقية تُدخل وتحذف رموزًا بدل مجرد تحريك نافذة ثابتة. طول LCS درجة تشابه مفيدة؛ والمحارف المُعاد بناؤها مفيدة حين تريدون هيكل محاذاة صريحًا بجانب الدرجة.
لا يعيد كل LCS الممكنة ولا سكربتات التعديل ولا نسب التشابه—فتلك مسائل منفصلة مبنية على فكرة جدول DP نفسها.
أين تُجدي واجهة LCS نفعًا حقيقيًا
تحتاج مقررات علوم الحاسوب والحكام عبر الإنترنت إلى أوراكل مرجعي يعيد طولًا صحيحًا وتتابعًا صالحًا لسلاسل قصيرة اعتباطية دون أن يلصق الطلاب حلولًا في IDE كامل. ميزات المنتج القريبة من diff—ملخصات التغيير، تلميحات تعارض الدمج، محاذاة أسطر السجل—غالبًا ما تريد طول LCS إشارة تشابه رخيصة قبل مرور أثقل لمسافة التحرير. عروض التدريس في المعلوماتية الحيوية تستخدم سلاسل أبجدية DNA لعبية (A وC وG وT) لتبيّن كيف تترك الإدراجات والحذوفات مع ذلك عمودًا فقريًا مشتركًا طويلًا.
تستفيد مواقع المحتوى التي تتنافس على حاسبة أطول تتابع مشترك من ودجت مجاني حيّ تطابق وحدته الخالصة مسار الأتمتة المدفوع بايتًا ببايت. أبقوا السلاسل دون سقف الطول، وثبّتوا التتابع المُعاد بناؤه في الاختبارات إن كان يهمكم أي الإجابات متساوية الطول تحصلون عليها، فتحصلون على نتائج LCS قابلة للتكرار دون إقامة مكتبة عددية خاصة بكم.
حالات الاستخدام
واجبات الخوارزميات وعروض المحاضرات
أعطوا الطلاب سلسلتين قصيرتين وتحققوا من طول LCS ومن أن التتابع المُعاد يظهر فعلًا بالترتيب في كل إدخال.
التصحيح الآلي في LMS والمسابقات
صحّحوا مهام DP بأوراكل حتمي يرفض الإدخال غير الصالح ولا يخترع أبدًا تتابعًا أطول مما يسمح به الجدول الكلاسيكي.
فحوصات diff وتشابه التسلسل المسبقة
قيّموا البنية المرتبة المشتركة بين نصين أو سلاسل DNA لعبية قبل مسار أثقل لمسافة التحرير أو المحاذاة.
الأسئلة الشائعة
هل LCS هو نفسه أطول سلسلة فرعية مشتركة؟
لا. يجب أن تكون السلسلة الفرعية متجاورة؛ أما التتابع فيجوز له تخطي محارف. تحل هذه الحاسبة مسألة التتابع بالبرمجة الديناميكية الكلاسيكية.
ما حدود الطول وقواعد السلسلة الفارغة؟
يجوز لكل سلسلة 500 محرفًا كحد أقصى. السلاسل الفارغة مسموحة وتنتج length 0 مع تتابع فارغ.
لماذا قد يوجد أكثر من أطول تتابع مشترك واحد؟
لأن التعادل شائع. فالنصان ABCBDAB وBDCABA يتشاركان عدة تتابعات طولها 4، مثل BCBA وBDAB. وتعيد الحاسبة واحدًا منها وتحسم التعادل بالطريقة نفسها دائمًا، فيعطي الزوج نفسه الإجابة نفسها.
فيمَ يفيد طول التتابع المشترك؟
يصلح مقياسًا سريعًا للتشابه، إذ تستعمله ملخصات التغييرات وتلميحات الدمج ومحاذاة أسطر السجلات قبل حساب مسافة تحرير أثقل، وتوضح أمثلة الحمض النووي كيف يبقى جزء مشترك طويل رغم الإدراج والحذف.
كيف أتحقق من صحة التتابع المُعاد؟
تأكد من أن أحرفه تظهر بالترتيب نفسه في النصين مع تخطي غيرها، وأن طوله يطابق الرقم المذكور. فالتتابع BCBA يتحقق في ABCBDAB وفي BDCABA، وهكذا تُصحَّح الإجابات.
أدوات ذات صلة
للمطوّرين — الوصول عبر API
كل ما في هذه الصفحة متاح برمجيًا. هذا القسم موجّه للفرق التقنية التي تريد ربط الأداة بأنظمتها الخاصة؛ بقية المستخدمين يمكنهم استخدام الأداة أعلاه مباشرة دون الحاجة لقراءة ما يلي.
الـEndpoint
صادِق على طلبك بترويسة Bearer، وأرسل طلب POST واحدًا لتدخل مهمتك قائمة التنفيذ فورًا؛ ثم تستلم النتيجة عبر 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"
}
}الواجهة غير متزامنة: تستلم task_id فور الإرسال، ويمكنك الاستعلام عن الحالة بمعدل طلب واحد في الثانية.
الأسعار
السعر معلن كما تراه: لا tokens ولا نظام نقاط؛ وإن فشلت المهمة فلن تُحاسَب عليها.
الأخطاء
| HTTP | الرمز | المعنى |
|---|---|---|
401 | unauthorized | مفتاح الوصول مفقود أو غير صالح؛ تحقق من ترويسة Bearer في طلبك. |
402 | insufficient_balance | رصيدك لا يكفي لتنفيذ هذه المهمة؛ أعد شحن الرصيد ثم أعد المحاولة. |
404 | unknown_type | نوع المهمة المطلوب غير موجود في الكتالوج — راجع الاسم المرسل في الطلب. |
429 | rate_limited | تجاوزت الحد المسموح من الطلبات؛ انتظر قليلًا ثم أعد المحاولة. |
ملاحظات تقنية
المنطق التحليلي الخالص نفسه يعمل مجانًا في ودجت المتصفح وكاستدعاء API مدفوع، فلا تختلف أوراكل الواجبات ولا سكربتات التصحيح ولا عمّال الحافة في الإنتاج على مثال كتابي ABCD.
عقد الإدخال والخوارزمية وشكل الاستجابة والحدود
تُحدَّ كل سلسلة بخمس مئة وحدة ترميز UTF-16 ليبقى الجدول التربيعي محدودًا في الودجت المجاني وفي بيئة الحافة. أرسلوا جسم JSON بطريقة POST بحقلين سلسلتين مطلوبين: string_a وstring_b (تُقبل الأسماء البديلة a وs1 وfirst وtext_a وb وs2 وsecond وtext_b). يجوز أن يكون كلاهما فارغًا؛ ويجب أن يكونا سلسلتي JSON حقيقيتين لا أرقامًا ولا مصفوفات. الحقول الناقصة والأنواع غير السلاسل والمدخلات الطويلة جدًا تفشل بـ invalid_input ولا تُفوتر. عند النجاح يعيد الجسم string_a وstring_b، ويبلّغ len_a وlen_b، ويتضمن length (طول LCS) وsubsequence (سلسلة LCS واحدة، قد تكون فارغة). داخليًا يخصص الحلّ جدول أعداد صحيحة (m+1) في (n+1)، ويضبط dp[i][j] إلى dp[i-1][j-1]+1 عند تطابق البادئات في آخر محرف، وإلا إلى أقصى الخليتين العليا واليسرى، ثم يسير من الزاوية السفلى اليمنى: الزوج المطابق يضيف ذلك المحرف ويتحرك قطريًا؛ وعند التعادل يفضّل الصعود (إسقاط من string_a) لتكون النسخة المُعاد بناؤها مستقرة عبر بيئات التشغيل.
أين تُجدي واجهة LCS نفعًا حقيقيًا
يمكن لمصحّحي LMS الآليين استدعاء API بأزواج ثابتة والتحقق من الطول ومن أن التتابع المُعاد تتابع لكل إدخال، فيلتقطون أخطاء جدول الواحد التي تفشل فقط في الحالات الفارغة أو ذات المحرف الواحد. ولأن التنفيذ parse خالص من المستوى A، يكلف كل استدعاء ناجح السعر الأساسي المنشور $0.002 بلا رموز نموذج ولا شبكة صادرة.
أسئلة تقنية
كيف أحسب أطول تتابع مشترك لسلسلتين؟
أرسلوا string_a وstring_b كسلسلتي JSON. تعيد API الحقل length (طول LCS) وsubsequence (تتابعًا مشتركًا أعظميًا واحدًا)، مع المدخلات المُعادة وأطوالها.
أي LCS يُعاد عند وجود عدة حلول؟
أي LCS بطول أعظمي صحيح. تستخدم هذه التنفيذ رجوعًا ثابتًا (تفضيل إسقاط string_a عند التعادل) فتعطي المدخلات نفسها دائمًا سلسلة التتابع نفسها.
كم تكلفة حاسبة أطول تتابع مشترك؟
أداة المتصفح مجانية. تستخدم طلبات API رصيد KIT المدفوع مسبقًا بسعر $0.002 لكل استدعاء ناجح؛ الإدخال غير الصالح لا يُفوتر.