আহো-কোরাসিক অ্যালগরিদম#

আহো-কোরাসিক অ্যালগরিদম আমাদের একটি টেক্সটে দ্রুত একাধিক প্যাটার্ন সার্চ করতে দেয়। প্যাটার্ন স্ট্রিং-এর সেটকে ডিকশনারি ও বলা হয়। আমরা এর উপাদান স্ট্রিংগুলোর মোট দৈর্ঘ্যকে $m$ এবং বর্ণমালার আকারকে $k$ দিয়ে চিহ্নিত করব। অ্যালগরিদমটি $O(m k)$ সময়ে একটি ট্রাই-ভিত্তিক ফিনাইট স্টেট অটোমেটন তৈরি করে এবং তারপর টেক্সট প্রক্রিয়া করতে এটি ব্যবহার করে।

অ্যালগরিদমটি ১৯৭৫ সালে আলফ্রেড আহো এবং মার্গারেট কোরাসিক প্রস্তাব করেন।

ট্রাই তৈরি#


"Java", "Rad", "Rand", "Rau", "Raum" এবং "Rose" শব্দের উপর ভিত্তি করে একটি ট্রাই।
The image by [nd](https://de.wikipedia.org/wiki/Benutzer:Nd) is distributed under CC BY-SA 3.0 license.

আনুষ্ঠানিকভাবে, একটি ট্রাই হলো একটি রুটেড ট্রি, যেখানে ট্রির প্রতিটি এজ কোনো অক্ষর দ্বারা লেবেলযুক্ত এবং একটি ভার্টেক্স থেকে বের হওয়া এজগুলোর লেবেল ভিন্ন।

আমরা ট্রাইয়ের প্রতিটি ভার্টেক্সকে রুট থেকে সেই ভার্টেক্স পর্যন্ত পথের লেবেল দিয়ে গঠিত স্ট্রিং দ্বারা চিহ্নিত করব।

প্রতিটি ভার্টেক্সে একটি ফ্ল্যাগ $\text{output}$ ও থাকবে যা সেট করা হবে যদি ভার্টেক্সটি ডিকশনারির একটি প্যাটার্নের সাথে সম্পর্কিত হয়।

তদনুযায়ী, স্ট্রিং-এর একটি সেটের জন্য একটি ট্রাই হলো এমন ট্রাই যেন প্রতিটি $\text{output}$ ভার্টেক্স সেটের একটি স্ট্রিং-এর সাথে এবং বিপরীতভাবে সেটের প্রতিটি স্ট্রিং একটি $\text{output}$ ভার্টেক্সের সাথে সম্পর্কিত।

আমরা এখন বর্ণনা করি কিভাবে প্রদত্ত স্ট্রিং-এর সেটের জন্য তাদের মোট দৈর্ঘ্যের সাপেক্ষে লিনিয়ার সময়ে একটি ট্রাই তৈরি করতে হয়।

আমরা ট্রির ভার্টেক্সের জন্য একটি স্ট্রাকচার পরিচয় করাই:

const int K = 26;

struct Vertex {
    int next[K];
    bool output = false;

    Vertex() {
        fill(begin(next), end(next), -1);
    }
};

vector<Vertex> trie(1);

এখানে, আমরা ট্রাইকে $\text{Vertex}$-এর একটি অ্যারে হিসেবে সংরক্ষণ করি। প্রতিটি $\text{Vertex}$-এ ফ্ল্যাগ $\text{output}$ এবং $\text{next}[]$ অ্যারে আকারে এজ আছে, যেখানে $\text{next}[i]$ হলো সেই ভার্টেক্সের ইনডেক্স যেখানে $i$ অক্ষর অনুসরণ করে পৌঁছানো যায়, অথবা $-1$ যদি এরকম কোনো এজ না থাকে। প্রাথমিকভাবে, ট্রাই শুধু একটি ভার্টেক্স নিয়ে গঠিত - রুট - যার ইনডেক্স $0$।

এখন আমরা একটি ফাংশন ইমপ্লিমেন্ট করি যা ট্রাইয়ে একটি স্ট্রিং $s$ যোগ করবে। ইমপ্লিমেন্টেশন সরল: আমরা রুট নোড থেকে শুরু করি, এবং যতক্ষণ $s$-এর অক্ষরের সাথে সম্পর্কিত এজ আছে ততক্ষণ সেগুলো অনুসরণ করি। যদি কোনো অক্ষরের জন্য এজ না থাকে, আমরা একটি নতুন ভার্টেক্স তৈরি করি এবং একটি এজ দিয়ে সংযুক্ত করি। প্রক্রিয়ার শেষে আমরা শেষ ভার্টেক্সটিকে ফ্ল্যাগ $\text{output}$ দিয়ে চিহ্নিত করি।

void add_string(string const& s) {
    int v = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[v].next[c] == -1) {
            trie[v].next[c] = trie.size();
            trie.emplace_back();
        }
        v = trie[v].next[c];
    }
    trie[v].output = true;
}

এই ইমপ্লিমেন্টেশন স্পষ্টতই লিনিয়ার সময়ে চলে, এবং যেহেতু প্রতিটি ভার্টেক্স $k$ লিংক সংরক্ষণ করে, এটি $O(m k)$ মেমোরি ব্যবহার করবে।

প্রতিটি ভার্টেক্সে অ্যারের পরিবর্তে ম্যাপ ব্যবহার করে মেমোরি খরচ $O(m)$-এ কমানো সম্ভব। তবে, এতে টাইম কমপ্লেক্সিটি $O(m \log k)$-এ বাড়বে।

একটি অটোমেটন তৈরি#

ধরুন আমরা প্রদত্ত স্ট্রিং-এর সেটের জন্য একটি ট্রাই তৈরি করেছি। এখন এটিকে ভিন্ন দৃষ্টিকোণ থেকে দেখি। যদি আমরা যেকোনো ভার্টেক্স দেখি, এর সাথে সম্পর্কিত স্ট্রিংটি সেটের এক বা একাধিক স্ট্রিং-এর একটি প্রিফিক্স, তাই ট্রাইয়ের প্রতিটি ভার্টেক্সকে সেটের এক বা একাধিক স্ট্রিং-এ একটি অবস্থান হিসেবে ব্যাখ্যা করা যায়।

আসলে, ট্রাই ভার্টেক্সগুলোকে একটি ফিনাইট ডিটারমিনিস্টিক অটোমেটনের স্টেট হিসেবে ব্যাখ্যা করা যায়। যেকোনো স্টেট থেকে আমরা ট্রানজিশন করতে পারি - কোনো ইনপুট অক্ষর ব্যবহার করে - অন্য স্টেটে, অর্থাৎ স্ট্রিং-এর সেটে অন্য অবস্থানে। উদাহরণস্বরূপ, যদি ডিকশনারিতে শুধু একটি স্ট্রিং $abc$ থাকে, এবং আমরা ভার্টেক্স $ab$-তে দাঁড়িয়ে আছি, তাহলে অক্ষর $c$ ব্যবহার করে আমরা ভার্টেক্স $abc$-তে যেতে পারি।

তাই আমরা ট্রাইয়ের এজগুলোকে সংশ্লিষ্ট অক্ষর অনুযায়ী অটোমেটনে ট্রানজিশন হিসেবে বুঝতে পারি। তবে, একটি অটোমেটনে প্রতিটি স্টেট এবং অক্ষরের সমন্বয়ের জন্য ট্রানজিশন থাকতে হবে। যদি আমরা কোনো অক্ষর দিয়ে ট্রানজিশন করতে চাই, এবং ট্রাইয়ে সংশ্লিষ্ট এজ না থাকে, তাহলেও আমাদের কোনো স্টেটে যেতে হবে।

আরও সুনির্দিষ্টভাবে, ধরুন আমরা একটি স্ট্রিং $t$-এর সাথে সম্পর্কিত স্টেটে আছি, এবং আমরা $c$ অক্ষর ব্যবহার করে ভিন্ন স্টেটে ট্রানজিশন করতে চাই। যদি এই অক্ষর $c$ দিয়ে লেবেলযুক্ত এজ থাকে, তাহলে আমরা সরাসরি এই এজ ধরে $t + c$-এর সাথে সম্পর্কিত ভার্টেক্সে যেতে পারি। যদি এরকম কোনো এজ না থাকে, যেহেতু আমরা এই ইনভ্যারিয়েন্ট বজায় রাখতে চাই যে বর্তমান স্টেট হলো প্রক্রিয়াকৃত স্ট্রিং-এ দীর্ঘতম আংশিক মিল, আমাদের ট্রাইয়ে স্ট্রিং $t$-এর প্রকৃত সাফিক্স যেটি দীর্ঘতম সেটি খুঁজতে হবে, এবং সেখান থেকে ট্রানজিশনের চেষ্টা করতে হবে।

উদাহরণস্বরূপ, ট্রাই $ab$ এবং $bc$ স্ট্রিং দিয়ে তৈরি, এবং আমরা বর্তমানে $ab$-এর সাথে সম্পর্কিত ভার্টেক্সে আছি, যেটি একটি $\text{output}$ ভার্টেক্সও। $c$ অক্ষর দিয়ে ট্রানজিশন করতে, আমরা $b$ স্ট্রিং-এর সাথে সম্পর্কিত স্টেটে যেতে বাধ্য, এবং সেখান থেকে $c$ অক্ষরের এজ অনুসরণ করতে বাধ্য।


"a", "ab", "bc", "bca", "c" এবং "caa" শব্দের উপর ভিত্তি করে একটি আহো-কোরাসিক অটোমেটন।
নীল তীরগুলো সাফিক্স লিংক, সবুজ তীরগুলো টার্মিনাল লিংক।

একটি ভার্টেক্স $p$-এর জন্য সাফিক্স লিংক হলো একটি এজ যা ভার্টেক্স $p$-এর সাথে সম্পর্কিত স্ট্রিং-এর দীর্ঘতম প্রকৃত সাফিক্সের দিকে নির্দেশ করে। একমাত্র বিশেষ ক্ষেত্র হলো ট্রাইয়ের রুট, যার সাফিক্স লিংক নিজের দিকেই নির্দেশ করবে। এখন আমরা অটোমেটনের ট্রানজিশন সম্পর্কিত বিবৃতিটি এভাবে পুনর্গঠন করতে পারি: যতক্ষণ ট্রাইয়ের বর্তমান ভার্টেক্স থেকে বর্তমান অক্ষর দিয়ে কোনো ট্রানজিশন নেই (অথবা রুটে না পৌঁছানো পর্যন্ত), আমরা সাফিক্স লিংক অনুসরণ করি।

তাই আমরা অটোমেটন তৈরির সমস্যাটিকে ট্রাইয়ের সকল ভার্টেক্সের জন্য সাফিক্স লিংক খোঁজার সমস্যায় রিডিউস করেছি। তবে, আমরা এই সাফিক্স লিংকগুলো, আশ্চর্যজনকভাবে, অটোমেটনে তৈরি ট্রানজিশন ব্যবহার করে তৈরি করব।

রুট ভার্টেক্স এবং এর সকল তাৎক্ষণিক চিলড্রেনের সাফিক্স লিংক রুট ভার্টেক্সের দিকে নির্দেশ করে। ট্রিতে আরও গভীরে যেকোনো ভার্টেক্স $v$-এর জন্য, সাফিক্স লিংক নিম্নরূপে গণনা করা যায়: যদি $p$ হলো $v$-এর পূর্বসূরি এবং $c$ হলো $p$ থেকে $v$-তে যাওয়ার এজের অক্ষর, $p$-তে যান, তারপর এর সাফিক্স লিংক অনুসরণ করুন, এবং সেখান থেকে $c$ অক্ষর দিয়ে ট্রানজিশন করুন।

তাই, ট্রানজিশন খোঁজার সমস্যা সাফিক্স লিংক খোঁজার সমস্যায় রিডিউস হয়েছে, এবং সাফিক্স লিংক খোঁজার সমস্যা একটি সাফিক্স লিংক এবং একটি ট্রানজিশন খোঁজার সমস্যায় রিডিউস হয়েছে, রুটের কাছের ভার্টেক্স ছাড়া। তাই আমাদের একটি রিকার্সিভ নির্ভরশীলতা আছে যা লিনিয়ার সময়ে সমাধান করা যায়।

আসুন ইমপ্লিমেন্টেশনে যাই। লক্ষ্য করুন এখন আমরা প্রতিটি ভার্টেক্স $v$-এর জন্য পূর্বসূরি $p$ এবং $p$ থেকে $v$-তে এজের অক্ষর $pch$ সংরক্ষণ করব। এছাড়া প্রতিটি ভার্টেক্সে সাফিক্স লিংক $\text{link}$ (বা $-1$ যদি এখনো গণনা না হয়ে থাকে), এবং $\text{go}[k]$ অ্যারেতে প্রতিটি প্রতীকের জন্য মেশিনে ট্রানজিশন (আবার $-1$ যদি এখনো গণনা না হয়ে থাকে) সংরক্ষণ করব।

const int K = 26;

struct Vertex {
    int next[K];
    bool output = false;
    int p = -1;
    char pch;
    int link = -1;
    int go[K];

    Vertex(int p=-1, char ch='$') : p(p), pch(ch) {
        fill(begin(next), end(next), -1);
        fill(begin(go), end(go), -1);
    }
};

vector<Vertex> t(1);

void add_string(string const& s) {
    int v = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (t[v].next[c] == -1) {
            t[v].next[c] = t.size();
            t.emplace_back(v, ch);
        }
        v = t[v].next[c];
    }
    t[v].output = true;
}

int go(int v, char ch);

int get_link(int v) {
    if (t[v].link == -1) {
        if (v == 0 || t[v].p == 0)
            t[v].link = 0;
        else
            t[v].link = go(get_link(t[v].p), t[v].pch);
    }
    return t[v].link;
}

int go(int v, char ch) {
    int c = ch - 'a';
    if (t[v].go[c] == -1) {
        if (t[v].next[c] != -1)
            t[v].go[c] = t[v].next[c];
        else
            t[v].go[c] = v == 0 ? 0 : go(get_link(v), ch);
    }
    return t[v].go[c];
}

সাফিক্স লিংক এবং ট্রানজিশনের মেমোয়াইজেশনের কারণে, সকল সাফিক্স লিংক এবং ট্রানজিশন খোঁজার মোট সময় লিনিয়ার হবে।

ধারণাটির চিত্রণের জন্য স্ট্যানফোর্ড স্লাইডের ১০৩ নম্বর স্লাইড দেখুন।

BFS-ভিত্তিক নির্মাণ#

go এবং get_link-এ রিকার্সিভ কল দিয়ে ট্রানজিশন এবং সাফিক্স লিংক গণনার পরিবর্তে, রুট থেকে শুরু করে বটম-আপ গণনা করা সম্ভব। (আসলে, যখন ডিকশনারিতে শুধু একটি স্ট্রিং থাকে, তখন আমরা পরিচিত নুথ-মরিস-প্র্যাট অ্যালগরিদম পাই।)

এই পদ্ধতির উপরে বর্ণিতটির তুলনায় কিছু সুবিধা আছে কারণ, মোট দৈর্ঘ্য $m$-এর পরিবর্তে, এর রানিং টাইম শুধু ট্রাইয়ের ভার্টেক্স সংখ্যা $n$-এর উপর নির্ভর করে। তাছাড়া, একটি পার্সিস্টেন্ট অ্যারে ডেটা স্ট্রাকচার ব্যবহার করে বড় বর্ণমালার জন্য এটি অভিযোজিত করা সম্ভব, ফলে নির্মাণ সময় $O(mk)$-এর পরিবর্তে $O(n \log k)$ হয়, যা উল্লেখযোগ্য উন্নতি কারণ $m$, $n^2$ পর্যন্ত হতে পারে।

আমরা ইনডাক্টিভভাবে যুক্তি দিতে পারি কারণ রুট থেকে BFS বর্ধমান দৈর্ঘ্যের ক্রমে ভার্টেক্সগুলো ট্র্যাভার্স করে। আমরা ধরে নিতে পারি যখন আমরা একটি ভার্টেক্স $v$-তে আছি, এর সাফিক্স লিংক $u = link[v]$ ইতিমধ্যে সফলভাবে গণনা করা হয়েছে, এবং ছোট দৈর্ঘ্যের সকল ভার্টেক্সের ট্রানজিশনও সম্পূর্ণরূপে গণনা করা হয়েছে।

ধরুন এই মুহূর্তে আমরা একটি ভার্টেক্স $v$-তে দাঁড়িয়ে আছি এবং একটি অক্ষর $c$ বিবেচনা করছি। মূলত আমাদের দুটি ক্ষেত্র আছে:

১. $go[v][c] = -1$। এই ক্ষেত্রে, আমরা $go[v][c] = go[u][c]$ অ্যাসাইন করতে পারি, যা ইনডাকশন হাইপোথিসিস অনুযায়ী ইতিমধ্যে জানা; ২. $go[v][c] = w \neq -1$। এই ক্ষেত্রে, আমরা $link[w] = go[u][c]$ অ্যাসাইন করতে পারি।

এভাবে, আমরা প্রতিটি ভার্টেক্স-অক্ষর জোড়ায় $O(1)$ সময় ব্যয় করি, ফলে রানিং টাইম $O(nk)$ হয়। এখানে প্রধান ওভারহেড হলো প্রথম ক্ষেত্রে $u$ থেকে অনেক ট্রানজিশন কপি করা, যখন দ্বিতীয় ক্ষেত্রের ট্রানজিশনগুলো ট্রাই গঠন করে এবং সকল ভার্টেক্সে মিলিয়ে $n$ হয়। $go[u][c]$ কপি এড়াতে, আমরা একটি পার্সিস্টেন্ট অ্যারে ডেটা স্ট্রাকচার ব্যবহার করতে পারি, যেটি দিয়ে আমরা প্রথমে $go[u]$-কে $go[v]$-তে কপি করি এবং তারপর শুধু সেই অক্ষরগুলোর জন্য মান আপডেট করি যেখানে ট্রানজিশন ভিন্ন হবে। এটি $O(n \log k)$ অ্যালগরিদম দেয়।

অ্যাপ্লিকেশন#

একটি টেক্সটে প্রদত্ত সেটের সকল স্ট্রিং খোঁজা#

আমাদের একটি স্ট্রিং-এর সেট এবং একটি টেক্সট দেওয়া আছে। আমাদের $O(\text{len} + \text{ans})$ সময়ে প্রদত্ত টেক্সটে সেটের সকল স্ট্রিং-এর সকল উপস্থিতি প্রিন্ট করতে হবে, যেখানে $\text{len}$ হলো টেক্সটের দৈর্ঘ্য এবং $\text{ans}$ হলো উত্তরের আকার।

আমরা এই স্ট্রিং-এর সেটের জন্য অটোমেটন তৈরি করি। এখন আমরা অটোমেটন ব্যবহার করে টেক্সট অক্ষরে অক্ষরে প্রক্রিয়া করব, ট্রাইয়ের রুট থেকে শুরু করে। যদি আমরা যেকোনো সময়ে $v$ স্টেটে থাকি, এবং পরবর্তী অক্ষর $c$ হয়, তাহলে আমরা $\text{go}(v, c)$ দিয়ে পরবর্তী স্টেটে ট্রানজিশন করি, যার ফলে বর্তমান মিলিত সাবস্ট্রিং-এর দৈর্ঘ্য হয় $1$ বাড়ে, অথবা সাফিক্স লিংক অনুসরণ করে কমে।

$v$ স্টেটে কোনো মিল আছে কিনা কিভাবে জানব? প্রথমত, আমরা যদি একটি $\text{output}$ ভার্টেক্সে দাঁড়িয়ে থাকি, তাহলে ভার্টেক্সের সাথে সম্পর্কিত স্ট্রিং টেক্সটে এই অবস্থানে শেষ হয়। তবে এটি কোনোমতেই মিল অর্জনের একমাত্র সম্ভাব্য ক্ষেত্র নয়: যদি সাফিক্স লিংক ধরে এক বা একাধিক $\text{output}$ ভার্টেক্সে পৌঁছানো যায়, তাহলে প্রতিটি পাওয়া $\text{output}$ ভার্টেক্সের জন্যও একটি মিল থাকবে। $\{dabce, abc, bc\}$ স্ট্রিং-এর সেট এবং $dabc$ টেক্সট দিয়ে এই পরিস্থিতি প্রদর্শনকারী একটি সরল উদাহরণ তৈরি করা যায়।

তাই যদি আমরা প্রতিটি $\text{output}$ ভার্টেক্সে সম্পর্কিত স্ট্রিং-এর ইনডেক্স (বা ডুপ্লিকেট থাকলে ইনডেক্সের তালিকা) সংরক্ষণ করি, তাহলে আমরা $O(n)$ সময়ে বর্তমান স্টেটে মিলিত সকল স্ট্রিং-এর ইনডেক্স খুঁজতে পারি, কেবল বর্তমান ভার্টেক্স থেকে রুট পর্যন্ত সাফিক্স লিংক অনুসরণ করে। এটি সবচেয়ে দক্ষ সমাধান নয়, কারণ এতে সামগ্রিকভাবে $O(n ~ \text{len})$ কমপ্লেক্সিটি হয়। তবে, সাফিক্স লিংক দিয়ে পৌঁছানো নিকটতম $\text{output}$ ভার্টেক্স গণনা ও সংরক্ষণ করে এটি অপটিমাইজ করা যায় (এটিকে কখনো কখনো এক্সিট লিংক বলা হয়)। এই মান আমরা লেজিলি লিনিয়ার সময়ে গণনা করতে পারি। তাই প্রতিটি ভার্টেক্সের জন্য আমরা $O(1)$ সময়ে সাফিক্স লিংক পথে পরবর্তী চিহ্নিত ভার্টেক্সে, অর্থাৎ পরবর্তী মিলে অগ্রসর হতে পারি। তাই প্রতিটি মিলের জন্য আমরা $O(1)$ সময় ব্যয় করি, এবং তাই কমপ্লেক্সিটি $O(\text{len} + \text{ans})$-এ পৌঁছাই।

আপনি যদি শুধু উপস্থিতির সংখ্যা গণনা করতে চান এবং ইনডেক্স নিজে না চান, তাহলে প্রতিটি ভার্টেক্স $v$-এর জন্য সাফিক্স লিংক পথে চিহ্নিত ভার্টেক্সের সংখ্যা গণনা করতে পারেন। এটি মোট $O(n)$ সময়ে গণনা করা যায়। তাই সকল মিল $O(\text{len})$-এ যোগ করা যায়।

প্রদত্ত দৈর্ঘ্যের লেক্সিকোগ্রাফিক্যালি ক্ষুদ্রতম স্ট্রিং খোঁজা যা কোনো প্রদত্ত স্ট্রিং-এর সাথে মেলে না#

স্ট্রিং-এর একটি সেট এবং একটি দৈর্ঘ্য $L$ দেওয়া আছে। আমাদের $L$ দৈর্ঘ্যের এমন একটি স্ট্রিং খুঁজতে হবে, যাতে কোনো স্ট্রিং নেই, এবং এরকম স্ট্রিংগুলোর মধ্যে লেক্সিকোগ্রাফিক্যালি ক্ষুদ্রতমটি বের করতে হবে।

আমরা স্ট্রিং-এর সেটের জন্য অটোমেটন তৈরি করতে পারি। মনে রাখুন $\text{output}$ ভার্টেক্সগুলো হলো সেই স্টেট যেখানে সেটের কোনো স্ট্রিং-এর সাথে মিল আছে। যেহেতু এই কাজে আমাদের মিল এড়াতে হবে, আমরা এরকম স্টেটে প্রবেশ করতে পারি না। অন্যদিকে অন্য সকল ভার্টেক্সে প্রবেশ করা যায়। তাই আমরা মেশিন থেকে সকল “খারাপ” ভার্টেক্স মুছে দিই, এবং অটোমেটনের অবশিষ্ট গ্রাফে $L$ দৈর্ঘ্যের লেক্সিকোগ্রাফিক্যালি ক্ষুদ্রতম পথ খুঁজি। এই কাজটি $O(L)$-এ সমাধান করা যায় উদাহরণস্বরূপ ডেপথ ফার্স্ট সার্চ দিয়ে।

সকল প্রদত্ত স্ট্রিং ধারণকারী সংক্ষিপ্ততম স্ট্রিং খোঁজা#

এখানে আমরা একই ধারণা ব্যবহার করি। প্রতিটি ভার্টেক্সের জন্য আমরা একটি মাস্ক সংরক্ষণ করি যা নির্দেশ করে এই স্টেটে কোন স্ট্রিংগুলো মেলে। তাহলে সমস্যাটি নিম্নরূপে পুনর্গঠন করা যায়: প্রাথমিকভাবে $(v = \text{root},~ \text{mask} = 0)$ স্টেটে থেকে, আমরা $(v,~ \text{mask} = 2^n - 1)$ স্টেটে পৌঁছাতে চাই, যেখানে $n$ হলো সেটে স্ট্রিং-এর সংখ্যা। যখন আমরা একটি অক্ষর ব্যবহার করে এক স্টেট থেকে অন্য স্টেটে ট্রানজিশন করি, আমরা সেই অনুযায়ী মাস্ক আপডেট করি। ব্রেডথ ফার্স্ট সার্চ চালিয়ে আমরা ক্ষুদ্রতম দৈর্ঘ্যের $(v,~ \text{mask} = 2^n - 1)$ স্টেটে পৌঁছানোর পথ খুঁজতে পারি।

$L$ দৈর্ঘ্যের লেক্সিকোগ্রাফিক্যালি ক্ষুদ্রতম স্ট্রিং খোঁজা যাতে $k$ স্ট্রিং আছে#

পূর্ববর্তী সমস্যার মতো, আমরা প্রতিটি ভার্টেক্সের জন্য এর সাথে সম্পর্কিত মিলের সংখ্যা গণনা করি (অর্থাৎ সাফিক্স লিংক ব্যবহার করে পৌঁছানো চিহ্নিত ভার্টেক্সের সংখ্যা)। আমরা সমস্যাটি পুনর্গঠন করি: বর্তমান স্টেট তিনটি সংখ্যার ট্রিপল $(v,~ \text{len},~ \text{cnt})$ দ্বারা নির্ধারিত, এবং আমরা $(\text{root},~ 0,~ 0)$ স্টেট থেকে $(v,~ L,~ k)$ স্টেটে পৌঁছাতে চাই, যেখানে $v$ যেকোনো ভার্টেক্স হতে পারে। তাই আমরা ডেপথ ফার্স্ট সার্চ দিয়ে এরকম পথ খুঁজতে পারি (এবং যদি সার্চ এজগুলো তাদের স্বাভাবিক ক্রমে দেখে, তাহলে পাওয়া পথ স্বয়ংক্রিয়ভাবে লেক্সিকোগ্রাফিক্যালি ক্ষুদ্রতম হবে)।

সমস্যা#

রেফারেন্স#