Lexicographically minimal string rotation
কম্পিউটার বিজ্ঞানে, অভিধানগতভাবে ন্যূনতম স্ট্রিং ঘূর্ণন বা অভিধানগতভাবে সর্বনিম্ন বৃত্তাকার সাবস্ট্রিং হল এই ধরনের সমস্ত ঘূর্ণনের সর্বনিম্ন অভিধানগত ক্রম ধারণকারী একটি স্ট্রিংয়ের ঘূর্ণন খুঁজে বের করার সমস্যা। উদাহরণস্বরূপ, অভিধানগতভাবে "বাবাক্কাদ"-এর ন্যূনতম আবর্তন হবে "আক্কাড্ডব"। একটি স্ট্রিংয়ের জন্য একাধিক অভিধানগতভাবে ন্যূনতম ঘূর্ণন সম্ভব, তবে বেশিরভাগ প্রয়োগের জন্য এটি কোন ব্যাপার না কারণ ঘূর্ণনগুলি অবশ্যই সমতুল্য হতে হবে। অভিধানগতভাবে ন্যূনতম ঘূর্ণন খুঁজে পাওয়া স্ট্রিংকে স্বাভাবিক করার একটি উপায় হিসাবে কার্যকর। যদি স্ট্রিংগুলি গ্রাফের মতো সম্ভাব্য আইসোমরফিক কাঠামোর প্রতিনিধিত্ব করে, তবে এইভাবে স্বাভাবিককরণ সহজ সমতা পরীক্ষার অনুমতি দেয়। বৃত্তাকার স্ট্রিং নিয়ে কাজ করার সময় একটি সাধারণ বাস্তবায়ন কৌশল হল স্ট্রিং সূচকগুলিতে মডুলার পাটিগণিত সম্পাদন করার পরিবর্তে স্ট্রিংটিকে নিজের সাথে সংযুক্ত করা। অ্যালগরিদম নিষ্ক্রিয় অ্যালগরিদম একটি স্ট্রিংয়ের অভিধানগতভাবে ন্যূনতম ঘূর্ণন খুঁজে বের করার জন্য সরল অ্যালগরিদম হল অভিধানগতভাবে সবচেয়ে ন্যূনতম ঘূর্ণনের উপর নজর রাখার সময় ধারাবাহিক ঘূর্ণনের মাধ্যমে পুনরাবৃত্তি করা। যদি স্ট্রিংটি দৈর্ঘ্যের হয়, তবে এই অ্যালগরিদমটি সবচেয়ে খারাপ ক্ষেত্রে সময়মতো চলে। বুথের অ্যালগরিদম একটি দক্ষ অ্যালগরিদম বুথ (1980) দ্বারা প্রস্তাবিত হয়েছিল। অ্যালগরিদমটি নুথ-মরিস-প্র্যাট স্ট্রিং সার্চ অ্যালগরিদম থেকে একটি পরিবর্তিত প্রিপ্রসেসিং ফাংশন ব্যবহার করে। স্ট্রিংয়ের ব্যর্থতা ফাংশনটি স্বাভাবিক হিসাবে গণনা করা হয়, তবে গণনার সময় স্ট্রিংটি ঘোরানো হয় তাই কিছু সূচকগুলি মোড়ানোর সময় একাধিকবার গণনা করা আবশ্যক। একবার ব্যর্থতা ফাংশনের সমস্ত সূচকগুলি স্ট্রিংটি আবার ঘোরানো ছাড়াই সফলভাবে গণনা করা হয়ে গেলে, ন্যূনতম অভিধানগত ঘূর্ণন পাওয়া যায় এবং এর প্রারম্ভিক সূচকটি ফেরত দেওয়া হয়। অ্যালগরিদমের সঠিকতা বোঝা কিছুটা কঠিন, তবে এটি বাস্তবায়ন করা সহজ। ডেফ লিস্ট _ রোটেশন (এসঃ এসআর)-> ইন্টেঃ "" বুথের লেক্সিকোগ্রাফিকভাবে ন্যূনতম স্ট্রিং রোটেশন অ্যালগরিদম "।" n = লেন (গুলি) 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) একটি অ্যালগরিদম প্রস্তাব করেছিলেন যাতে স্বাভাবিককরণের প্রয়োজনীয়তা ছাড়াই সমতার জন্য দুটি বৃত্তাকার স্ট্রিংয়ের দক্ষতার সাথে তুলনা করা যায়। অ্যালগরিদম থেকে উদ্ভূত একটি অতিরিক্ত প্রয়োগ হল পুনরাবৃত্তি ছাড়াই নির্দিষ্ট রাসায়নিক কাঠামোর দ্রুত প্রজন্ম। আরও দেখুন লিন্ডন শব্দ ক্নুথ-মরিস-প্র্যাট অ্যালগরিদম রেফারেন্স সমস্যা স্ট্রিং-এ লেক্সিকোগ্রাফি উদাহরণ কোড সহ নিবন্ধ