Rotation and Queries

Subtask 1:

প্রথম সাবটাস্কের জন্য ব্রুটফোর্স ইউজ করা যেতে পারে।

অ্যাক্সেপ্টেবল কমপ্লেক্সিটিঃ O($n^3$)

Subtask 2:

সাবটাস্ক ২ এর জন্য প্রত্যেকটি রোটেশন জেনারেট এবং সেগুলো সর্ট করে রাখা যেতে পারে। এনালাইসিস করলে একটা ফ্যাক্ট পাওয়া যাবে যে, $i^{th}$ তম রোটেশনে ইনপুট স্ট্রিং এর X সাইজের সব সাফিক্স সাবস্ট্রিং হিসেবে থাকে, যেখানে X = (ইনপুট স্ট্রিং এর সাইজ - i)। এই ফ্যাক্ট থেকে প্রত্যেকটা কুয়েরির উপর কাজ করতে হবে।

অ্যাক্সেপ্টেবল কমপ্লেক্সিটিঃ O($n^2$)

Subtask 3:

সাবটাস্ক ৩ এর জন্য পুরা স্ট্রিং এর শেষ ক্যারেকটার বাদে স্ট্রিং টি ইনপুট স্ট্রিং এর শেষে যুক্ত করতে হবে। এরপরে সাফিক্স অ্যারে (Suffix array - Wikipedia) এলগোরিদম চালাতে হবে। সেখানে যেসব সাফিক্স এর লেংথ ইনপুট স্ট্রিং এর সমান বা বড় সেগুলার সাফিক্স অ্যারে রিভার্স অর্ডারে স্টোর করতে হবে। সো, তোমার কাছে বর্তমানে একটা L (যেখানে, L = ইনপুট স্ট্রিং এর লেংথ) সাইজের অ্যারে আছে যেটা লেক্সিকোগ্রাফিক্যাল অর্ডার এর রিভার্স অর্ডারে (সবচেয়ে বড় সাফিক্স প্রথমে আসবে) রোটেশন গুলার ইনডেক্স অফ রোটেশন ( স্টেটমেন্ট এ ডিফাইন করা আছে) স্টোর করে। এই রিভার্স সাফিক্স অ্যারে থেকে একটা নতুন অ্যারে তৈরী করতে হবে যার প্রত্যেকটি এলিমেন্ট সেই এলিমেন্ট পর্যন্ত পাওয়া সবচেয়ে ছোট ইনডেক্স অফ রোটেশন স্টোর করে। এখন এই অ্যারে এর উপর বাইনারী সার্চ করে প্রত্যেকটা কুয়েরির উত্তর করতে হবে। এই ক্ষেত্রে, $i^{th}$ তম রোটেশনে ইনপুট স্ট্রিং এর X সাইজের সব সাফিক্স সাবস্ট্রিং হিসেবে থাকে, যেখানে X = (ইনপুট স্ট্রিং এর সাইজ - i) ফ্যাক্টটি ব্যবহার করতে হবে।

অ্যাক্সেপ্টেবল কমপ্লেক্সিটিঃ O($n log_2(n)$)