Lexicographically minimal string rotation
کمپیوٹر سائنس میں، لغت کے لحاظ سے کم سے کم تار کی گردش یا لغت کے لحاظ سے کم سے کم سرکلر سبسٹرنگ اس طرح کی تمام گردشوں کی سب سے کم لغت کی ترتیب رکھنے والی تار کی گردش کو تلاش کرنے کا مسئلہ ہے۔ مثال کے طور پر، "باکاڈ" کی لغت کے لحاظ سے کم سے کم گردش "آکاڈب" ہوگی۔ کسی سٹرنگ کے لیے یہ ممکن ہے کہ اس میں متعدد لغت کے لحاظ سے کم سے کم گردش ہو، لیکن زیادہ تر ایپلی کیشنز کے لیے اس سے کوئی فرق نہیں پڑتا کیونکہ گردش مساوی ہونی چاہیے۔ لغت کے لحاظ سے کم سے کم گردش تلاش کرنا تاروں کو معمول پر لانے کے طریقے کے طور پر مفید ہے۔ اگر تار ممکنہ طور پر آئسومورفک ڈھانچوں جیسے گراف کی نمائندگی کرتے ہیں، تو اس طرح سے معمول بنانا مساوات کی آسان جانچ کی اجازت دیتا ہے۔ سرکلر سٹرنگز سے نمٹنے کے دوران عمل درآمد کی ایک عام چال یہ ہے کہ سٹرنگ انڈیکس پر ماڈیولر ریاضی انجام دینے کے بجائے سٹرنگ کو خود سے جوڑنا ہے۔ الگورتھم غیر فعال الگورتھم سٹرنگ کی لغت کے لحاظ سے کم سے کم گردش کو تلاش کرنے کے لیے بے وقوف الگورتھم یہ ہے کہ لغت کے لحاظ سے کم سے کم گردش کا سامنا کرتے ہوئے مسلسل گردشوں کے ذریعے اس کا تکرار کیا جائے۔ اگر تار لمبائی کا ہے، تو یہ الگورتھم بدترین صورت میں وقت پر چلتا ہے۔ بوتھ کا الگورتھم ایک موثر الگورتھم بوتھ (1980) نے تجویز کیا تھا۔ الگورتھم نوتھ-موریس-پراٹ سٹرنگ سرچ الگورتھم سے ایک ترمیم شدہ پری پروسیسنگ فنکشن کا استعمال کرتا ہے۔ سٹرنگ کے لیے فیل فنکشن کو نارمل کے طور پر شمار کیا جاتا ہے، لیکن سٹرنگ کو کمپیوٹیشن کے دوران گھمایا جاتا ہے لہذا کچھ انڈیکس کو لپیٹتے وقت ایک سے زیادہ بار شمار کرنا ضروری ہے۔ ایک بار جب ناکامی فنکشن کے تمام اشاریہ جات کو تار کو دوبارہ گھومے بغیر کامیابی کے ساتھ شمار کر لیا جاتا ہے، تو کم سے کم لغت کی گردش معلوم ہوتی ہے اور اس کا ابتدائی اشاریہ واپس کر دیا جاتا ہے۔ الگورتھم کی درستگی کو سمجھنا کچھ مشکل ہے، لیکن اس پر عمل درآمد کرنا آسان ہے۔ "" بوتھ کا لغت کے لحاظ سے کم سے کم سٹرنگ گردش الگورتھم ""۔ n = لین (s) f = [-1] * (2 * n) k = 0 جے کے لیے رینج (1,2 * n) میں: i = f [j-k-1] جبکہ i! =-1 اور s [j% n]! = s [(k + i + 1)% n]: اگر s [j% n] <s [(k + i + 1)% n]: k = j-i = f [i] اگر i = = اور s [j% n] = s [(k + i + 1)% n]: اگر s [j% n] <s [(k + i + 1)% n]: k = بوتھ کا الگورتھم وقت پر چلتا ہے، تار کی لمبائی کہاں ہے۔ الگورتھم بدترین صورت میں زیادہ تر موازنہ کرتا ہے، اور ناکامی فنکشن ٹیبل کو برقرار رکھنے کے لیے لمبائی کی معاون میموری کی ضرورت ہوتی ہے۔ شیلوچ کے فاسٹ کینونائزیشن الگورتھم شیلوچ (1981) نے کارکردگی کے لحاظ سے بوتھ کے نتائج کو بہتر بنانے کے لیے ایک الگورتھم کی تجویز پیش کی۔ یہ مشاہدہ کیا گیا کہ اگر لمبائی کی تار کی مساوی لغت کے لحاظ سے کم سے کم گردش ہوتی ہے، تو تار لمبائی کے مساوی سبسٹرنگ پر مشتمل ہونا چاہیے۔ الگورتھم کو بدترین صورت میں صرف موازنہ اور مستقل جگہ کی ضرورت ہوتی ہے۔ الگورتھم کو دو مراحل میں تقسیم کیا گیا ہے۔ پہلا مرحلہ ایک تیز چھلنی ہے جو اشاریہ جات کو مسترد کرتی ہے جو ظاہر ہے کہ لغت کے لحاظ سے کم سے کم گردش کے لیے ابتدائی مقامات نہیں ہیں۔ دوسرا مرحلہ پھر باقی انڈیکس سے لغت کے لحاظ سے کم سے کم گردش شروع انڈیکس تلاش کرتا ہے۔ ڈوول کے لنڈن فیکٹرائزیشن الگورتھم ڈوول (1983) نے ایک موثر الگورتھم کی تجویز پیش کی جس میں سٹرنگ کو اس کے جزو لنڈن ورڈز میں فیکٹرائزیشن شامل ہے، جو مستقل میموری کی ضرورت کے ساتھ لکیری وقت میں چلتا ہے۔ متغیرات شیلوچ (1979) نے معمول کی ضرورت کے بغیر مساوات کے لیے دو سرکلر تاروں کا مؤثر طریقے سے موازنہ کرنے کے لیے ایک الگورتھم کی تجویز پیش کی۔ الگورتھم سے پیدا ہونے والی ایک اضافی ایپلی کیشن بعض کیمیائی ڈھانچوں کی تیز رفتار نسل ہے جو بغیر تکرار کے ہوتی ہے۔ لنڈن لفظ نوتھ-موریس-پراٹ الگورتھم بھی دیکھیں حوالہ جات تاروں پر مسائل لغت مثال کوڈ کے ساتھ مضامین