بالنظر إلى قائمة من السلاسل، ابحث عن كل زوج $ (x، y) $ حيث $ x $ هو لاحق $ y $ $.ممكن أن تفعل أفضل من $ (n ^ 2) $؟

Question

النظر في مشكلة الخوارزميات التالية: إعطاء قائمة من السلاسل $ l= [s_1، s_2، \ dots، s_n] $ ، نريد أن نعرف جميع أزواج < Span Class="حاوية الرياضيات"> $ (x، y) $ حيث $ x $ هو لاحق $ y $ . يمكننا أن نفترض أن جميع الأوتار مدة الطول عند الحد الأقصى $ m $ ، حيث $ m << n $ و هل في جميع أنحاء الأبجدية المحدودة $ \ Sigma $ مع $ | \ sigma | << N $ . قد نفترض أيضا أن عدد أزواج $ (x، y) $ حيث $ x $ هو لاحق $ y $ هو أصغر بكثير من $ n $ .

خوارزمية تافهة سيكون هذا:

giveacodicetagpre.

ومع ذلك، هذا لديه تعقيد $ O (n ^ 2 \ cdot m) $ - أنا فضولي لمعرفة ما إذا كانت هناك خوارزمية أسرع (أسرع بالنظر إلى ذلك عدد أزواج $ (x، y) $ أصغر بكثير من $ n $ ، لذلك على سبيل المثال خوارزمية مع تعقيد اعتمادا على عدد أزواج الإخراج).

لاحظ أن هذا السؤال هو متابعة هذا السؤال ، وهو ما يتعلق بنفس المشكلة ولكن بالنسبة للبالغين (وليس لاحق). هناك، حل خوارزمية AHO-CORASICK حل مشكلتي تماما - هل ربما يكون هناك شيء من هذا القبيل ولكن بالنسبة لاحقات؟

Answer 1

لا، فمن غير الممكن أن تفعل أفضل ما لم تفرض فرضية الوقت الأسي القوي (Seth). إذا استطعنا حل هذه المشكلة بشكل كبير أسرع من $ O (n ^ 2) $ سنحصل على الفور الحصول على خوارزمية أسرع بكثير لحل تلبية مشكلة NP-Complete. هذا صحيح حتى بالنسبة ل $ m $ أكثر قليلا من $ \ log (n) $ والحالة في الذي نريد أن نقرر ما إذا كان هذا الزوج $ (x، y) $ موجود على الإطلاق.

انظر، على سبيل المثال، ملاحظات هذه المحاضرات تحت القسم 3 "ضيق انخفاض الحدود لنوع المهام ". والدليل هو مماثل لإثبات نظرية 2 في هذه الملاحظات المحاضرة.

أولا، نعتبر مشكلة أكثر عمومية من مجموعتين من السلاسل $ x، $ $ ، والعثور على ما إذا كانت بعض السلسلة في $ x $ هو لاحق سلسلة في $ y $ .

تعطى صيغة السبت، نقسم $ n $ المتغيرات إلى مجموعتين متساويين من $ n / 2 $ < / تمتد> المتغيرات. في $ \ Sigma $ نأخذ شخصية مقابلة لكل جملة. في $ X $ نضيف سلسلة لكل مهمة ممكنة إلى النصف الأول من المتغيرات، مع حرف مقابلة لكل جملة غير راضية من قبل هذه المتغيرات. وفي الوقت نفسه، في $ y $ ، نقوم بإضافة سلسلة لكل مهمة إلى النصف الثاني من المتغيرات، مع حرف لكل جملة راضية بتلك المتغيرات. من الواضح أن الصيغة راضية إذا وفقط إذا كانت بعض السلسلة في $ x $ هي لاحقا بعض السلسلة في $ y $ .

إذا كانت هذه المشكلة يمكن حلها بشكل أسرع بكثير من $ O (n ^ 2) $ ، ثم يعطي هذا خوارزمية أسرع إلى حد كبير للرضا عن $ 2 ^ n $ . لنفترض أن المشكلة يمكن حلها في $ O (n ^ {1.99}) $ الوقت، ثم يمكن حل الرضا في $ (2 ^ {n / 2}) ^ {1.99}= o (2 ^ {0.996n}) $ الذي يتناقض مع سيث.

في مشكلتك، لا يوجد سوى مجموعة واحدة من السلاسل، والتي قد تكون كلها لاحقا لبعضها البعض. ولكن هذا ليس مشكلة، حيث يمكننا ببساطة تعديل السلاسل في مثيلنا بحيث لا توجد سلسلة $ y $ هي لاحقا لأي سلسلة أخرى (على سبيل المثال عن طريق الحشو جميع الأوتار في $ y للحصول على نفس الطول)، والحشو بالمثل كل سلسلة في $ x $ $ x $ (ولكن أقصر بشكل كبير من السلاسل في $ y $ ) .

قد يحدث هذا أيضا بحجم أبجدية ثابتة (محتملة حتى ثنائية) ولكن هذا يتطلب ترميز أكثر ذكاء.