সাফিক্স অ্যারে এবং এলসিপি অ্যারে (Suffix Array & LCP Array)

ধরুন একটা শব্দ হলো "জাম"। এর ৬টা সাফিক্স (suffix) বা শেষাংশ আছে: "জাম", "anana", "nana", "ana", "na", "a"। এখন এই অংশগুলোকে যদি ইংরেজি ডিকশনারির নিয়মে (alphabetically) ছোট থেকে বড় হিসেবে সাজান এবং মূল শব্দে তাদের শুরুর ইনডেক্সগুলো লিখে রাখেন, তবে ওই ইনডেক্সগুলোর লিস্টটাকেই বলা হয় সাফিক্স অ্যারে (Suffix Array)।

"জাম"-এর জন্য সাজানেন লিস্টটা হবে এরকম:

• 5 → "a"
• 3 → "ana"
• 1 → "anana"
• 0 → "জাম"
• 4 → "na"
• 2 → "nana"

সাফিক্স অ্যারেটা দেখতে হবে শুধু শুরুর ইনডেক্সগুলোর একটা লিস্ট: [5, 3, 1, 0, 4, 2]। খেয়াল রাখবেন, এখানে সত্যিকারের শব্দগুলো (যেমন "ana", "nana") কিন্তু সেভ করা হয় না — দরকার পড়লে ইনডেক্স ধরে মূল শব্দ থেকে সেগুলো বের করে নেওয়া হয়। এর ফলেই মেমোরি খরচ একদম কম (মাত্র O(n)) থাকে।

অ্যারে বানানো: প্রিফিক্স ডাবলিং (Prefix doubling) — O(n log n)

সাধারণ বা বোকা (naive) পদ্ধতিতে সবগুলো সাফিক্সকে স্ট্রিং কম্পেয়ার করে সাজাতে গেলে O(n) সংখ্যক অক্ষর মেলাতে হয়, ফলে মোট সময় লাগে O(n² log n)। বড় শব্দের ক্ষেত্রে এটা মারাত্মক স্লো।

১৯৯০ সালে ম্যানবার ও মায়ার্স (Manber & Myers) একটা বুদ্ধি বের করেন, যার নাম প্রিফিক্স ডাবলিং (Prefix doubling) — এটা দিয়ে O(n log n) সময়েই কাজটা হয়ে যায়। এর মূল আইডিয়া হলো:

1. প্রথমে সবগুলো সাফিক্সকে শুধু তাদের প্রথম ১টা অক্ষরের ওপর ভিত্তি করে র‍্যাঙ্ক (rank) বা সাজানেন হয়।
2. এরপর প্রতি রাউন্ডে তুলনার দৈর্ঘ্য ডাবল বা দ্বিগুণ করা হয়: অর্থাৎ ২টা অক্ষর, এরপর ৪টা, তারপর ৮টা... এভাবে সাজানেন হয়।
3. এভাবে মাত্র log₂(n) রাউন্ড চলার পরই সবগুলো সাফিক্স আলাদা করা হয়ে যায় এবং পুরো অ্যারে গোছানো কমপ্লিট হয়ে যায়।

প্রতি রাউন্ডে র‍্যাডিক্স সর্ট (radix sort) ব্যবহার করায় প্রতিটা রাউন্ডে মাত্র O(n) সময় লাগে। তাই মোট সময়: O(n log n) রাউন্ড × O(n) = O(n log n)।

এলসিপি অ্যারে (LCP Array — Longest Common Prefix)

সাফিক্স অ্যারের সাথেই আরেকটা জিনিস বানানো হয়, যার নাম এলসিপি অ্যারে (LCP array)। lcp[i] মানে হলো: সাজানেন লিস্টে 'i' নম্বর সাফিক্স এবং তার ঠিক আগের '(i-1)' নম্বর সাফিক্সের মধ্যে প্রথম দিককার ঠিক কয়টা অক্ষর হুবহু সেম বা কমন আছে।

"জাম"-এর জন্য LCP হলো: [-, 1, 3, 0, 0, 2] (০ নম্বর পজিশনের আগে কেউ নেই; "a" আর "ana"-এর মধ্যে প্রথম ১টি অক্ষর কমন; "ana" আর "anana"-এর মধ্যে প্রথম ৩টি অক্ষর কমন ইত্যাদি)।

কোথায় কাজে লাগে এই সাফিক্স + এলসিপি?

• প্যাটার্ন খোঁজা (Pattern search): সাফিক্স অ্যারের ওপর বাইনারি সার্চ চালিয়ে খুব সহজেই যেকোনো প্যাটার্ন খুঁজে বের করা যায়। সময় লাগে O(m log n), যেখানে m হলো প্যাটার্নের দৈর্ঘ্য।
• সবচেয়ে বড় রিপিট হওয়া শব্দ (Longest repeated substring): এলসিপি অ্যারের মধ্যে সবচেয়ে বড় যে সংখ্যাটা, সেটাই হলো মূল শব্দের ভেতর সবচেয়ে বড় রিপিট হওয়া অংশ।
• কয়টা আলাদা সাবস্ট্রিং আছে (Distinct substrings): সাবস্ট্রিংয়ের মোট সম্ভাব্য সংখ্যা n(n+1)/2 থেকে এলসিপি অ্যারের সব সংখ্যার যোগফল বাদ দিলেই উত্তর পাওয়া যায়।