List of Strings

এই সমস্যাটা সমাধান করার জন্য অন্তত দুটি ডাটা স্ট্রাকচার লাগবে: একটি ট্রাই এবং অপরটি সেগমেন্ট ট্রি অথবা বিআইটি। সমস্যাটি সমাধান করার ধাপগুলো নিম্নরূপ:

১. সবগুলো কোয়েরি একসাথে নিয়ে সেভ করে রাখো। এভাবে আগে থেকে সব কোয়েরি নিয়ে রেখে পরে উত্তর দেবার কৌশলকে “অফলাইন কোয়েরি হ্যান্ডেলিং” বলা হয়। কেননা, কোন কোয়েরি পাবার পর সাথে সাথেই উত্তর না দিয়ে সব কোয়েরি একবারে নিয়ে পরে উত্তর দেওয়া হয়।

২. সবগুলো স্ট্রিংকে ট্রাইতে ঢুকাই। স্ট্রিংগুলো কোথায় শেষ হয়েছে সেই জায়গাগুলোর জন্য ট্রাইয়ের মধ্যের নোডগুলোতে চিহ্ন দিয়ে রাখি। এছাড়া স্ট্রিংগুলোতে ট্রাইতে রাখার সময় ট্রাইয়ের কোন নোড কতবার ভিজিট হয়েছে সেটা মনে রাখি।

৩. এবারে ট্রাইয়ের নোডগুলোর উপরে ডিএফএস চালাই এবং সবগুলো নোডের ডিএফএস টাইম বের করি। ডিএফএস এমনভাবে চালাবো যাবে লেক্সিকোগ্রাফিকালি ছোট প্রিফিক্স নির্দেশকারী নোডের ডিএফএস টাইম কম হয়।

৪. কিউমুলেটিভ সাম নেবার জন্য আমরা একটা বাইনারি ইনডেক্স ট্রি নেই যেখান ট্রাইয়ের নোডগুলোর ফ্রিকোয়েন্সি সেভ করে রাখি।

৫. এরপর আমরা টাইপ ২ এবং টাইপ ৩ কোয়েরিগুলোর উত্তর দিতে পারি:

ক. যদি টাইপ ২ কোয়েরি পাই তাহলে স্ট্রিংয়ের শেষ অবস্থান নির্দেশকারী ট্রাইয়ের নোড থেকে উপরের দিকে যাই এবং যেতে যেতে বাইনারি ইনডেক্স ট্রি এর ডাটা আপডেট করি।

খ. যদি টাইপ এ কোয়েরি পাই, তাহলে দুটো স্ট্রিংয়ের শেষ অবস্থান নির্দেশকারী ট্রাইয়ের নোড দুটির ডিএফএস টাইম দেখি। এরপর এই দুটি নোডের ডিএফএস টাইমের যোগফল নিয়ে প্রিন্ট করি।