Suffix array, LCP আর Aho-Corasick

১ · একটি লেখা, হাজারো প্রশ্ন — suffix কেন চাবি

পর্ব ৫৮-এ KMP বা Z algorithm দিয়ে একটি লেখা T-এর (দৈর্ঘ্য n) ভেতরে একটি pattern P (দৈর্ঘ্য m) খুঁজেছেন O(n + m) সময়ে। কিন্তু ভাবুন, লেখাটি একটি বড় অভিধান, একটি আইনের বই বা একটি জীবের পুরো DNA — আর একই লেখার ওপর প্রতিদিন লাখো আলাদা প্রশ্ন আসে। প্রতিবার পুরো লেখা নতুন করে পড়া মানে প্রতিটি প্রশ্নে O(n). এখানে বুদ্ধি হলো উল্টো দিকে খাটা: লেখাটিকে একবার গুছিয়ে রাখুন, যাতে পরে প্রতিটি প্রশ্নের খরচ মূলত শুধু pattern-এর দৈর্ঘ্যের ওপর নির্ভর করে।

গোছানোর চাবি হলো suffix: কোনো একটি অবস্থান থেকে লেখার শেষ পর্যন্ত অংশ। “banana”-র suffix ছয়টি — banana, anana, nana, ana, na, a. এখন একটি সরল কিন্তু শক্তিশালী পর্যবেক্ষণ:

পর্ব ৩১-এ দেখেছেন, T-এর সব suffix একটি trie-তে ঢোকালে পাওয়া যায় suffix trie: যেকোনো P খোঁজা O(m), কারণ শুধু P-এর অক্ষর ধরে নামতে হয়। সমস্যা জায়গায় — suffix-গুলোর মোট দৈর্ঘ্য n(n+1)/2, তাই worst case-এ Θ(n²) node. দশ লাখ অক্ষরের লেখায় সেটি প্রায় ৫০,০০০ কোটি node — অসম্ভব।

সমাধানের প্রথম ধাপ radix tree-র কৌশল: একা-সন্তানের শিকলগুলো জুড়ে একটি edge বানানো, আর edge-এর label-কে মূল লেখার (শুরু, শেষ) index হিসেবে রাখা। এতে পাওয়া যায় suffix tree — n টি leaf আর বড়জোর n − 1 টি শাখা-node, অর্থাৎ O(n) জায়গা। একে O(n) সময়ে বানানোর পদ্ধতি দিয়েছেন Peter Weiner (১৯৭৩), পরে কম জায়গায় Edward McCreight (১৯৭৬), আর বাঁ থেকে ডানে এক পাসে Esko Ukkonen (১৯৯৫). এই পদ্ধতিগুলো সুন্দর কিন্তু জটিল; এই পর্বে আমরা এদের নাম জেনেই থামব।

২ · Suffix array — সব suffix সাজিয়ে শুধু শুরুর index

Suffix tree-র O(n) জায়গাও বাস্তবে বড়: প্রতিটি node-এ কয়েকটি pointer আর index, ফলে অক্ষরপ্রতি কয়েক ডজন byte. ১৯৯০ সালে Udi Manber আর Gene Myers প্রস্তাব করেন অনেক সরল একটি স্ট্রাকচার: suffix array — সব suffix-কে lexicographic order-এ (অভিধানের ক্রমে) সাজিয়ে শুধু তাদের শুরুর index-গুলো একটি অ্যারেতে রাখা। অক্ষরপ্রতি মাত্র একটি পূর্ণসংখ্যা। নিচে “banana” দিয়ে দেখুন (0-based index).

এর সাথে প্রায়ই রাখা হয় উল্টো অ্যারে rank array: rank[i] = i থেকে শুরু suffix-টি সাজানো তালিকার কোন সারিতে। banana-য় rank = [3, 2, 5, 1, 4, 0], কারণ sa[3] = 0, sa[2] = 1, ইত্যাদি। দুটি অ্যারে একে অন্যের inverse: sa[rank[i]] = i.

সবচেয়ে সরল নির্মাণ. 0 থেকে n − 1 পর্যন্ত index নিন আর এমন comparator দিয়ে sort করুন, যা দুটি index-এর suffix অক্ষর ধরে তুলনা করে। Sort-এ O(n log n) টি তুলনা (পর্ব ২১), আর প্রতিটি তুলনা worst case-এ O(n) অক্ষর পড়ে — যেমন “aaaa…a”-তে প্রায় সব তুলনা লম্বা। মোট O(n² log n) সময়, বাড়তি জায়গা O(n). কয়েক হাজার অক্ষরের জন্য যথেষ্ট, আর ছোট ইনপুটে উত্তর মেলানোর জন্য দারুণ brute force. কিন্তু n = ১০^৫ হলে এটি কনটেস্টের সময়সীমা পার হয়ে যায়।

৩ · Prefix doubling — ১, ২, ৪, ৮ অক্ষর ধরে সাজানো

Naive পদ্ধতির অপচয় হলো, প্রতিটি তুলনা একই অক্ষরগুলো বারবার পড়ে। Prefix doubling (Manber ও Myers-এর মূল প্রবন্ধের ধারণা; Karp, Miller আর Rosenberg-এর ১৯৭২ সালের কৌশলের ওপর দাঁড়ানো) আগের কাজ কাজে লাগায়। ধরুন প্রতিটি suffix i-এর জন্য আমরা জানি rank_k[i] — শুধু প্রথম k টি অক্ষর ধরলে সে সাজানো ক্রমে কোথায় (প্রথম k অক্ষর সমান হলে rank-ও সমান)। তাহলে প্রথম 2k অক্ষরের তুলনা আসলে একটি জোড়ার তুলনা:

কারণ প্রথম 2k অক্ষর = প্রথম k অক্ষর, তারপর i + k থেকে শুরু আরও k অক্ষর। i + k লেখার বাইরে গেলে দ্বিতীয় ভাগ খালি, আর খালি সবার চেয়ে ছোট — তাই সেখানে −1 বসান। জোড়াগুলো sort করে পাশাপাশি তুলনা করলেই নতুন rank_2k. প্রতি ধাপে দৈর্ঘ্য দ্বিগুণ, আর যখন সব rank আলাদা হয়ে যায়, ক্রম চূড়ান্ত।

Pseudocode — prefix doubling (0-based; rank[j] = -1 when j >= n)

suffixArray(T[0..n-1]):
    sa = [0, 1, ..., n-1];  rank[i] = code of T[i]
    k = 1
    loop:
        key(i) = (rank[i], rank[i + k])          // first 2k characters of suffix i
        sort sa by key
        new[sa[0]] = 0
        for t = 1 .. n-1:
            new[sa[t]] = new[sa[t-1]] + (key(sa[t-1]) < key(sa[t]) ? 1 : 0)
        rank = new
        if rank[sa[n-1]] == n-1: return sa       // all ranks distinct
        k = 2k

কেন এটি ঠিক. Invariant: k-এর ধাপ শেষে rank[i] < rank[j] ⇔ suffix i-এর প্রথম 2k অক্ষর suffix j-এর প্রথম 2k অক্ষরের চেয়ে অভিধানে ছোট (খালি অংশকে সবচেয়ে ছোট ধরে). শুরুতে এক অক্ষরের জন্য এটি সংজ্ঞা থেকেই সত্য। ধাপ থেকে ধাপে: 2k অক্ষরের তুলনা = আগে প্রথম k-এর তুলনা, সমান হলে পরের k-এর — ঠিক জোড়ার lexicographic তুলনা, আর দুই ভাগের তুলনা আগের invariant দেয়। সব rank আলাদা হলে আর কোনো দুটি suffix-এর ক্রম বদলাতে পারে না, কারণ ক্রম আগের অক্ষরেই ঠিক হয়ে গেছে। ২^t ≥ n হলে অবশ্যই থামে, কারণ পুরো suffix-ই তখন ধরা পড়ে আর দুটি আলাদা suffix-এর দৈর্ঘ্য আলাদা।

বিশ্লেষণ. ধাপ বড়জোর ⌈log₂ n⌉ + 1 টি। প্রতিটি ধাপে comparison sort O(n log n) (প্রতিটি তুলনা O(1), কারণ জোড়ার তুলনা) — মোট O(n log² n). কিন্তু rank-গুলো 0 থেকে n − 1-এর মধ্যে ছোট পূর্ণসংখ্যা, তাই comparison sort-এর বদলে পর্ব ২৪-এর radix sort চলে: আগে দ্বিতীয় ঘর ধরে, তারপর প্রথম ঘর ধরে দুটি stable counting sort, প্রতিটি O(n). তখন প্রতিটি ধাপ O(n), মোট O(n log n). জায়গা দুই ক্ষেত্রেই O(n). বাস্তবে আরও একটি শর্টকাট আছে: দ্বিতীয় ঘর ধরে সাজানো ক্রম আগের ধাপের sa থেকেই সরাসরি পড়ে নেওয়া যায়, তাই কনটেস্টের কোডে প্রায়ই একটি মাত্র counting sort থাকে।

৪ · Suffix array দিয়ে pattern খোঁজা — O(m log n)

অংশ ২-এর শেষ পর্যবেক্ষণটি এখন কাজে লাগবে। যে suffix-গুলো P দিয়ে শুরু, তারা সাজানো তালিকায় একটি টানা অংশ — ঠিক যেমন অভিধানে “ca” দিয়ে শুরু সব শব্দ পাশাপাশি। তাই দুটি binary search (পর্ব ১৮-এর lower bound আর upper bound) যথেষ্ট: প্রথম যে সারিতে suffix-এর প্রথম m অক্ষর ≥ P, আর প্রথম যে সারিতে তা > P. প্রতিটি তুলনায় বড়জোর m টি অক্ষর পড়তে হয়, আর তুলনা হয় O(log n) বার।

banana-য় P = “ana” খুঁজি। সাজানো suffix: a, ana, anana, banana, na, nana. প্রতিটি তুলনায় শুধু suffix-এর প্রথম ৩টি অক্ষর দেখা হয়:

সারি [L, R) = [1, 3), অর্থাৎ ২টি ঘটনা, শুরু sa[1] = 3 আর sa[2] = 1 — banana-র index 1 আর 3-এ “ana”, যা একটি আরেকটির ওপর পড়ে। খরচ: গোনা O(m log n); সব z টি অবস্থান লিখতে আরও O(z). লেখাটি একবার সাজানো থাকলে প্রতিটি নতুন প্রশ্নে n টি অক্ষর আর পড়তে হয় না, শুধু log n বার m অক্ষর। Manber ও Myers দেখিয়েছিলেন, পাশের অংশের LCP-র তথ্য আগে থেকে রাখলে এই খরচ O(m + log n)-এ নামে — কারণ binary search-এর সময় আগের তুলনায় মেলা অক্ষরগুলো আর পড়তে হয় না।

৫ · LCP array আর Kasai-এর O(n) অ্যালগরিদম

সাজানো suffix-গুলো পাশাপাশি কতটা মেলে, সেটিই বহু প্রশ্নের উত্তর। LCP array: lcp[r] = sa[r − 1] আর sa[r]-এর suffix দুটির longest common prefix-এর দৈর্ঘ্য (lcp[0] = 0 ধরি). banana-য় পাশাপাশি জোড়া: a/ana → 1, ana/anana → 3, anana/banana → 0, banana/na → 0, na/nana → 2. তাই lcp = [0, 1, 3, 0, 0, 2].

সরলভাবে প্রতিটি জোড়া প্রথম থেকে মেলালে worst case O(n²) — “aaaa…a”-তে lcp = 0, 1, 2, …, n − 1, যোগফল প্রায় n²/2. ২০০১ সালে Toru Kasai আর সহলেখকেরা (Lee, Arimura, Arikawa, Park) দেখান কীভাবে O(n)-এ পারা যায়। কৌশল: জোড়াগুলো সাজানো ক্রমে নয়, লেখার ক্রমে দেখুন — i = 0, 1, 2, … — আর আগের উত্তর থেকে শুরু করুন।

প্রমাণ. ধরুন j হলো সাজানো ক্রমে i-এর ঠিক আগের suffix, আর তারা প্রথম h অক্ষর ভাগ করে (h > 0). দুটির প্রথম অক্ষর এক বাদ দিলে suffix j + 1 আর i + 1 প্রথম h − 1 অক্ষর ভাগ করে। আর j < i (অভিধানে) এবং প্রথম অক্ষর এক, তাই j + 1 < i + 1 — অর্থাৎ সাজানো ক্রমে j + 1 আসে i + 1-এর আগে। এখন i + 1-এর ঠিক আগের suffix k সাজানো তালিকায় j + 1 আর i + 1-এর মাঝখানে (বা j + 1 নিজেই)। সাজানো তালিকায় দুটি suffix যে prefix ভাগ করে, মাঝখানের সবাই সেটি ভাগ করে — তাই k-ও i + 1-এর সাথে অন্তত h − 1 অক্ষর ভাগ করে। ∎

ফলে প্রতিটি i-এ h শূন্য থেকে নয়, আগের h − 1 থেকে মেলানো শুরু হয়। h কখনো n-এর বেশি হয় না আর প্রতিটি ধাপে বড়জোর ১ কমে, তাই সব ধাপ মিলিয়ে h বড়জোর n বার কমে — অতএব বাড়ে বড়জোর 2n বার। প্রতিটি সফল অক্ষর-মিল h এক বাড়ায়, প্রতিটি i-এ বড়জোর একটি ব্যর্থ মিল: মোট O(n) সময়, জায়গা rank আর lcp-এর জন্য O(n). (এই “potential কমে বড়জোর এতটুকু” ধরনের যুক্তি পর্ব ৬০-এর amortized analysis-এর একটি সুন্দর উদাহরণ।)

এবার দুটি অংশ একসাথে কোডে: prefix doubling-এ suffix array (সরলতার জন্য std::sort, তাই O(n log² n)) আর Kasai-এ LCP. তারপর পরের অংশের সূত্রে আলাদা substring গোনা হয় আর সব substring একটি set-এ রাখা brute force-এর সাথে মেলানো হয় — চারটি ভিন্ন ধাঁচের string-এ।

#include <algorithm>
#include <initializer_list>
#include <iostream>
#include <set>
#include <string>
#include <vector>
using namespace std;
vector<int> suffixArray(const string& s) {              // prefix doubling, O(n log^2 n)
    int n = s.size();
    vector<int> sa(n), rk(s.begin(), s.end()), tmp(n);   // round 0: rank = character code
    for (int i = 0; i < n; ++i) sa[i] = i;
    for (int k = 1; ; k *= 2) {
        auto key = [&](int i) { return pair(rk[i], i + k < n ? rk[i + k] : -1); };
        sort(sa.begin(), sa.end(), [&](int a, int b) { return key(a) < key(b); });
        tmp[sa[0]] = 0;
        for (int t = 1; t < n; ++t) tmp[sa[t]] = tmp[sa[t - 1]] + (key(sa[t - 1]) < key(sa[t]));
        rk = tmp;
        if (rk[sa[n - 1]] == n - 1) return sa;             // all ranks distinct: sorted
    }
}
vector<int> kasai(const string& s, const vector<int>& sa) {  // lcp[r] = LCP(sa[r-1], sa[r]), O(n)
    int n = s.size(), h = 0;
    vector<int> rk(n), lcp(n, 0);  for (int r = 0; r < n; ++r) rk[sa[r]] = r;
    for (int i = 0; i < n; ++i) {                        // suffixes in text order
        if (rk[i] == 0) { h = 0; continue; }
        int j = sa[rk[i] - 1];                           // the suffix just before i in sorted order
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) ++h;
        lcp[rk[i]] = h;
        if (h > 0) --h;                                  // key fact: the next LCP is at least h - 1
    }
    return lcp;
}
int main() {
    for (string w : {"banana", "abab", "aaaa", "mississippi"}) {
        auto sa = suffixArray(w); auto lcp = kasai(w, sa);
        long long n = w.size(), sum = 0; int b = 0;
        for (int r = 0; r < n; ++r) { sum += lcp[r]; if (lcp[r] > lcp[b]) b = r; }
        if (w == "banana") for (int r = 0; r < n; ++r) cout << r << ' ' << sa[r] << ' ' << lcp[r] << ' ' << w.substr(sa[r]) << '\n';
        set<string> all;                                 // brute force: every substring
        for (int i = 0; i < n; ++i) for (int l = 1; i + l <= n; ++l) all.insert(w.substr(i, l));
        cout << w << ": distinct " << n * (n + 1) / 2 - sum << ", brute " << all.size()
             << ", longest repeat '" << w.substr(sa[b], lcp[b]) << "'\n";
    }
}

0 5 0 a
1 3 1 ana
2 1 3 anana
3 0 0 banana
4 4 0 na
5 2 2 nana
banana: distinct 15, brute 15, longest repeat 'ana'
abab: distinct 7, brute 7, longest repeat 'ab'
aaaa: distinct 4, brute 4, longest repeat 'aaa'
mississippi: distinct 53, brute 53, longest repeat 'issi'

def suffix_array(s):                     # prefix doubling, O(n log^2 n)
    n = len(s)
    sa, rk = list(range(n)), [ord(c) for c in s]
    k = 1
    while True:
        key = lambda i: (rk[i], rk[i + k] if i + k < n else -1)
        sa.sort(key=key)
        tmp = [0] * n
        for t in range(1, n):
            tmp[sa[t]] = tmp[sa[t - 1]] + (key(sa[t - 1]) < key(sa[t]))
        rk = tmp
        if rk[sa[-1]] == n - 1: return sa  # all ranks distinct: sorted
        k *= 2

def kasai(s, sa):                        # lcp[r] = LCP(suffix sa[r-1], suffix sa[r]), O(n)
    n, h = len(s), 0
    rk, lcp = [0] * n, [0] * n
    for r, i in enumerate(sa): rk[i] = r
    for i in range(n):                   # suffixes in text order: i = 0, 1, 2, ...
        if rk[i] == 0: h = 0; continue
        j = sa[rk[i] - 1]                # the suffix just before i in sorted order
        while i + h < n and j + h < n and s[i + h] == s[j + h]: h += 1
        lcp[rk[i]] = h
        if h > 0: h -= 1                 # key fact: the next LCP is at least h - 1
    return lcp

for w in ["banana", "abab", "aaaa", "mississippi"]:
    sa = suffix_array(w); lcp = kasai(w, sa); n = len(w)
    if w == "banana":
        for r in range(n): print(r, sa[r], lcp[r], w[sa[r]:])
    brute = len({w[i:j] for i in range(n) for j in range(i + 1, n + 1)})   # every substring
    b = max(range(n), key=lambda r: lcp[r])   # first r with the largest LCP
    print(f"{w}: distinct {n * (n + 1) // 2 - sum(lcp)}, brute {brute}, longest repeat '{w[sa[b]:sa[b] + lcp[b]]}'")

0 5 0 a
1 3 1 ana
2 1 3 anana
3 0 0 banana
4 4 0 na
5 2 2 nana
banana: distinct 15, brute 15, longest repeat 'ana'
abab: distinct 7, brute 7, longest repeat 'ab'
aaaa: distinct 4, brute 4, longest repeat 'aaa'
mississippi: distinct 53, brute 53, longest repeat 'issi'

৬ · প্রয়োগ — আলাদা substring, longest repeated আর common substring

কতগুলো আলাদা substring?

দৈর্ঘ্য n-এর লেখায় মোট substring (একই লেখা বারবার গুনলে) n(n+1)/2 টি। কিন্তু “banana”-য় “a” তিনবার, “ana” দুবার — আলাদা substring কয়টি? Suffix array-র সারি ধরে ভাবুন: সারি r-এর suffix-এর দৈর্ঘ্য n − sa[r], তাই তার prefix n − sa[r] টি। এদের মধ্যে প্রথম lcp[r] টি আগের সারির suffix-এরও prefix — আগেই গোনা হয়েছে। বাকিগুলো একেবারে নতুন: কারণ আগের যেকোনো সারির সাথে মিল পাশের সারির চেয়ে বেশি হতে পারে না (সাজানো ক্রম)। তাই

banana: 21 − 6 = 15. Suffix array আর LCP বানাতে O(n log n), যোগফল O(n) — অথচ পর্ব ৩১-এর suffix trie-তে একই উত্তরের জন্য O(n²) node লাগত।

Longest repeated substring

যে substring লেখায় অন্তত দুবার আছে, সেটি দুটি আলাদা suffix-এর common prefix. আর সাজানো তালিকায় সবচেয়ে বেশি মেলে পাশের জোড়া — তাই longest repeated substring-এর দৈর্ঘ্য = max lcp[r], আর লেখাটি হলো T[sa[r]..sa[r] + lcp[r] − 1]. banana-য় সর্বোচ্চ lcp[2] = 3 — “ana” (দুটি ঘটনা একে অন্যের ওপর পড়ে, সেটি অনুমোদিত). mississippi-তে “issi”. খরচ O(n log n), naive পদ্ধতির O(n³)-এর তুলনায় বিশাল পার্থক্য।

দুটি string-এর longest common substring

দুটি লেখা s আর t-এর longest common substring চাই — যেমন দুটি প্রতিবেদনের মধ্যে সবচেয়ে লম্বা হুবহু কপি করা অংশ। কৌশল: মাঝে এমন একটি আলাদা অক্ষর দিয়ে জুড়ে দিন, যা দুটির কোনোটিতে নেই — u = s + “#” + t. এখন u-এর suffix array আর LCP বানান, আর এমন পাশাপাশি জোড়া খুঁজুন যাদের একটি s-এর ভেতরে শুরু (sa < |s|) আর অন্যটি t-এর ভেতরে। এমন জোড়ার সর্বোচ্চ lcp-ই উত্তর। “#” থাকায় কোনো common prefix দুই string-এর সীমা পার হতে পারে না, কারণ “#” একবারই আছে। “banana” আর “ananas”-এ উত্তর “anana” (দৈর্ঘ্য ৫). কেন শুধু পাশাপাশি জোড়া দেখলেই চলে? সেরা জোড়াটি (একটি s-এর, একটি t-এর) সাজানো তালিকায় যেখানেই থাকুক, তাদের মাঝখানে কোথাও না কোথাও s থেকে t-তে (বা উল্টো) একটি পাশাপাশি বদল আছে, আর সেই বদলের জোড়ার lcp অন্তত তাদের common prefix-এর সমান। খরচ O((|s| + |t|) log(|s| + |t|)), পর্ব ৫৪-এর DP-র O(|s|·|t|)-এর চেয়ে বড় ইনপুটে অনেক দ্রুত।

যেকোনো দুটি suffix-এর LCP. উপরের প্রমাণে বারবার একটি সত্য এসেছে: সারি a < b হলে suffix sa[a] আর sa[b]-এর LCP = min(lcp[a + 1..b]). এটি একটি range minimum query, তাই LCP array-র ওপর পর্ব ৩৭-এর sparse table বানালে O(n log n) প্রস্তুতির পর যেকোনো দুটি suffix-এর LCP O(1)-এ — কনটেস্টের অনেক কঠিন string সমস্যার মূল উপাদান।

৭ · অনেক pattern একসাথে — Aho-Corasick-এর trie আর failure link

এবার প্রশ্ন উল্টো। লেখা একটি, কিন্তু pattern অনেক — একটি মেসেজে কয়েক হাজার নিষিদ্ধ শব্দের কোনোটি আছে কি না, বা একটি ফাইলে লাখো পরিচিত ভাইরাসের কোনো চিহ্ন আছে কি না। প্রতিটি pattern-এর জন্য আলাদা KMP চালালে খরচ k টি pattern-এ O(k·n + m), যেখানে m = সব pattern-এর মোট দৈর্ঘ্য। ১৯৭৫ সালে Bell Labs-এর Alfred Aho আর Margaret Corasick দেখান কীভাবে লেখাটি একবার পড়েই সব pattern খোঁজা যায় — Aho-Corasick অ্যালগরিদম।

প্রথম ধাপ সহজ: সব pattern দিয়ে একটি trie বানান (পর্ব ৩১), আর যে node-এ কোনো pattern শেষ, সেখানে চিহ্ন রাখুন। লেখা পড়ার সময় trie-তে হাঁটুন। সমস্যা হলো মিল ভাঙলে কী করবেন। KMP-র উত্তর ছিল: এতক্ষণ যা মিলেছে, তার যে সবচেয়ে লম্বা অংশ শেষে আছে আর আবার একটি শুরু হিসেবে কাজে লাগে, সেখানে সরে যান। Aho-Corasick ঠিক এই ধারণাটিকে trie-তে নিয়ে যায়:

{he, she, his, hers}-এর trie-তে “she”-র node থেকে failure link যায় “he”-তে — কারণ “she” পড়া হলে শেষের “he”-ও পড়া হয়েছে, আর সেখান থেকে “hers” পর্যন্ত যাওয়া যেতে পারে। Link-গুলো বানানো হয় BFS দিয়ে, স্তর ধরে (পর্ব ৪০), কারণ fail(v) সবসময় v-এর চেয়ে অগভীর — তাই তার link আগেই জানা থাকে। নিয়ম: root-এর সন্তানদের fail = root. তারপর node v-এর c-অক্ষরের সন্তান u-এর জন্য fail(v) থেকে c-এর edge খুঁজুন; না পেলে fail(fail(v)) থেকে, এভাবে; root-এও না পেলে root.

কেন নিয়মটি ঠিক. u-এর string যদি Sc হয় (S = v-এর string, c একটি অক্ষর), তাহলে Sc-এর প্রতিটি proper suffix হয় খালি, নয়তো S′c — যেখানে S′ হলো S-এর একটি proper suffix. তাই প্রার্থী হলো S-এর trie-তে থাকা proper suffix-গুলো, লম্বা থেকে ছোট ক্রমে: f(v), f(f(v)), …, root — যার প্রথমটির c-edge আছে, সেটির c-সন্তানই উত্তর। এটি induction: অগভীর সব node-এর link ঠিক থাকলে u-এর link-ও ঠিক, আর BFS-এর ক্রম এই অনুমান নিশ্চিত করে।

Output link কেন লাগে. একই অবস্থানে কয়েকটি pattern শেষ হতে পারে (“she” আর “he”). সেগুলো পেতে fail-এর পুরো শিকল ধরে হাঁটা যায়, কিন্তু শিকলের বেশিরভাগ node হয়তো pattern-ই নয় — অপচয়। তাই প্রতিটি node-এ রাখা হয় out(v) = fail-শিকলে প্রথম যে node-এ pattern শেষ। তখন প্রতিটি লাফ একটি নতুন ঘটনা দেয়।

৮ · লেখা একবার পড়ে সব pattern — O(n + m + z)

খোঁজার নিয়ম: state = root. লেখার প্রতিটি অক্ষর c-এর জন্য, বর্তমান node-এ c-edge না থাকলে fail ধরে পিছিয়ে যান যতক্ষণ না পাওয়া যায় (বা root-এ পৌঁছান), তারপর c-edge ধরে নামুন। নতুন node নিজে pattern হলে রিপোর্ট করুন, তারপর output link-এর শিকল ধরে বাকিগুলো। নিচে লেখা “ahishers” (0-based index).

বিশ্লেষণ. Trie বানাতে O(m). খোঁজার সময় প্রতিটি fail-লাফ বর্তমান node-এর গভীরতা অন্তত ১ কমায়, আর প্রতিটি অক্ষর গভীরতা বড়জোর ১ বাড়ায় — তাই পুরো লেখায় মোট লাফ ≤ n, অর্থাৎ KMP-র মতোই amortized O(n). প্রতিটি output-লাফ একটি রিপোর্ট, তাই মোট O(n + m + z), z = মোট ঘটনার সংখ্যা। লক্ষ করুন z নিজে বড় হতে পারে — “aaaa…a” লেখায় {a, aa, aaa}-এর ঘটনা প্রায় 3n — তাই কোনো অ্যালগরিদম z-এর চেয়ে কম সময়ে সব ঘটনা লিখতে পারে না।

কনটেস্টের প্রচলিত কোড আরও এক ধাপ এগোয়: BFS-এর সময়ই প্রতিটি node আর প্রতিটি অক্ষরের জন্য চূড়ান্ত গন্তব্য হিসাব করে রাখে — node v-এ c-edge না থাকলে goto(v, c) = goto(fail(v), c). তখন খোঁজার লুপে একটিও fail-লাফ লাগে না, প্রতি অক্ষরে ঠিক একটি ধাপ। বিনিময়ে প্রস্তুতি আর জায়গা O(m·σ), σ = alphabet size. এটি আসলে একটি deterministic finite automaton (DFA). নিচের কোড এই রূপটিই বানায়।

#include <array>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
using namespace std;
int main() {
    vector<string> pats{"he", "she", "his", "hers"};
    vector<array<int, 26>> nxt(1); nxt[0].fill(-1);           // node 0 = root, -1 = no edge
    vector<int> fail{0}, out{-1}, word{-1};
    auto newNode = [&] { nxt.emplace_back(); nxt.back().fill(-1); fail.push_back(0); out.push_back(-1); word.push_back(-1); };
    for (int id = 0; id < (int)pats.size(); ++id) {           // 1) trie of all patterns
        int v = 0;
        for (char ch : pats[id]) {
            if (nxt[v][ch - 'a'] < 0) { nxt[v][ch - 'a'] = nxt.size(); newNode(); }
            v = nxt[v][ch - 'a'];
        }
        word[v] = id;
    }
    queue<int> q;                                             // 2) BFS: fail links + full goto table
    for (int c = 0; c < 26; ++c) { if (nxt[0][c] < 0) nxt[0][c] = 0; else q.push(nxt[0][c]); }
    while (!q.empty()) {
        int v = q.front(), f = fail[v]; q.pop();
        out[v] = word[f] >= 0 ? f : out[f];                   // nearest proper suffix that is a pattern
        for (int c = 0; c < 26; ++c) {
            int u = nxt[v][c];
            if (u < 0) nxt[v][c] = nxt[f][c];                 // missing edge: go where fail[v] goes
            else { fail[u] = nxt[f][c]; q.push(u); }
        }
    }
    cout << "nodes: " << nxt.size() << "  fail: [";
    for (size_t v = 0; v < fail.size(); ++v) cout << (v ? ", " : "") << fail[v];
    cout << "]\n";
    string text = "ahishers"; int v = 0, found = 0;           // 3) one pass over the text
    for (int i = 0; i < (int)text.size(); ++i) {
        v = nxt[v][text[i] - 'a'];
        for (int u = word[v] >= 0 ? v : out[v]; u > 0; u = out[u], ++found)   // every pattern ending at i
            cout << "'" << pats[word[u]] << "' at " << i - (int)pats[word[u]].size() + 1 << '\n';
    }
    cout << "matches: " << found << '\n';
}

nodes: 10  fail: [0, 0, 0, 0, 1, 2, 0, 3, 0, 3]
'his' at 1
'she' at 3
'he' at 4
'hers' at 4
matches: 4

from collections import deque
pats = ["he", "she", "his", "hers"]
nxt, fail, out, word = [[-1] * 26], [0], [-1], [-1]   # node 0 = root
for p_id, p in enumerate(pats):                       # 1) trie of all patterns
    v = 0
    for ch in p:
        c = ord(ch) - 97
        if nxt[v][c] < 0:
            nxt[v][c] = len(nxt); nxt.append([-1] * 26); fail.append(0); out.append(-1); word.append(-1)
        v = nxt[v][c]
    word[v] = p_id
q = deque()                                           # 2) BFS: fail links + full goto table
for c in range(26):
    if nxt[0][c] < 0: nxt[0][c] = 0
    else: q.append(nxt[0][c])
while q:
    v = q.popleft()
    f = fail[v]
    out[v] = f if word[f] >= 0 else out[f]            # nearest proper suffix that is a pattern
    for c in range(26):
        u = nxt[v][c]
        if u < 0: nxt[v][c] = nxt[f][c]               # missing edge: jump as fail[v] would
        else: fail[u] = nxt[f][c]; q.append(u)
print("nodes:", len(nxt), " fail:", fail)
text, v, found = "ahishers", 0, 0                     # 3) one pass over the text
for i, ch in enumerate(text):
    v = nxt[v][ord(ch) - 97]
    u = v if word[v] >= 0 else out[v]
    while u > 0:                                      # every pattern ending at position i
        p = pats[word[u]]
        print(f"'{p}' at {i - len(p) + 1}"); found += 1
        u = out[u]
print("matches:", found)

nodes: 10  fail: [0, 0, 0, 0, 1, 2, 0, 3, 0, 3]
'his' at 1
'she' at 3
'he' at 4
'hers' at 4
matches: 4

যেখানে Aho-Corasick রোজ চলে

Antivirus আর নেটওয়ার্ক নিরাপত্তা (প্রতিরক্ষা). একটি antivirus প্রতিটি ফাইলে হাজারো পরিচিত ক্ষতিকর byte-সারি (signature) খোঁজে; ClamAV-এর মতো open-source antivirus আর Snort-এর মতো intrusion detection system অনেক signature একসাথে মেলাতে Aho-Corasick বা তার রূপান্তর ব্যবহার করে। প্রতিটি নেটওয়ার্ক packet একবার পড়েই সব নিয়ম পরীক্ষা — signature বাড়লেও প্রতি byte-এ কাজ প্রায় একই থাকে। Spam আর নিষিদ্ধ শব্দ. মেসেজিং অ্যাপ বা অনলাইন মার্কেটপ্লেসের মন্তব্যে গালিগালাজ বা প্রতারণার চেনা বাক্য ধরা, ইমেইলের spam filter-এর চেনা শব্দ খোঁজা — সবই অনেক-pattern-এর সমস্যা। Unix-এর fgrep (আজকের grep -F) কয়েকটি স্থির string একসাথে খোঁজে; Aho নিজেই Unix-এর egrep আর fgrep লিখেছিলেন, আর fgrep-এ এই অ্যালগরিদমই ছিল।

৯ · AI-এর যুগে suffix structure — কোড ছোট, ভুল গভীরে

“Suffix array আর LCP-র কোড দাও” — AI কয়েক সেকেন্ডে কোড দেবে, আর ছোট উদাহরণে প্রায়ই সেটি চলবে। কিন্তু এই বিষয়ের ভুলগুলো লুকোয় সীমানায়: শেষে sentinel “$” রাখা না-রাখার গোলমাল, rank 0 থেকে নাকি 1 থেকে, Kasai-এ h কমাতে ভুলে যাওয়া (তখন উত্তর ঠিক থাকে কিন্তু O(n²) হয়ে যায়), Aho-Corasick-এ output link বাদ দিয়ে “she” পেলে “he” হারানো। আর complexity জিজ্ঞেস করলে AI প্রায়ই std::sort-এর doubling-কেও “O(n log n)” বলে দেয়।

এই বিষয়ে AI সাধারণত যেসব ভুল করে

Suffix structure-এর কোড যাচাইয়ের চেকলিস্ট

• ছোট string-এ suffix array naive sort-এর সাথে, আর LCP সরল অক্ষর-মেলানোর সাথে মিলিয়েছি
• Edge case চালিয়েছি: এক অক্ষরের string, সব অক্ষর এক (“aaaa”), পর্যায়বৃত্ত (“abab”), খালি pattern
• আলাদা substring-এর সংখ্যা set-ভিত্তিক brute force-এর সাথে কয়েকশো এলোমেলো string-এ মিলিয়েছি — stress testing
• সবচেয়ে বড় ইনপুটে (যেমন n = 10⁵, “aaaa…a”) সময় মেপেছি, যাতে O(n²) লুকিয়ে না থাকে
• Aho-Corasick-এর ফল প্রতিটি pattern-এ আলাদা naive খোঁজার ফলের সাথে মিলিয়েছি, overlap আর একটি pattern আরেকটির suffix — দুই ক্ষেত্রসহ
• AI-এর প্রতিটি complexity দাবি নিজে যাচাই করেছি: কোন sort, কতগুলো ধাপ, z আর σ কোথায়