প্রিফিক্স ফাংশন। নুথ-মরিস-প্র্যাট অ্যালগরিদম#

প্রিফিক্স ফাংশনের সংজ্ঞা#

আপনাকে $n$ দৈর্ঘ্যের একটি স্ট্রিং $s$ দেওয়া আছে। এই স্ট্রিং-এর প্রিফিক্স ফাংশন হলো $n$ দৈর্ঘ্যের একটি অ্যারে $\pi$ হিসেবে সংজ্ঞায়িত, যেখানে $\pi[i]$ হলো সাবস্ট্রিং $s[0 \dots i]$-এর দীর্ঘতম প্রকৃত প্রিফিক্সের দৈর্ঘ্য যেটি এই সাবস্ট্রিং-এর সাফিক্সও। একটি স্ট্রিং-এর প্রকৃত প্রিফিক্স হলো এমন প্রিফিক্স যা স্ট্রিং নিজেই নয়। সংজ্ঞা অনুযায়ী, $\pi[0] = 0$।

গাণিতিকভাবে প্রিফিক্স ফাংশনের সংজ্ঞা নিম্নরূপে লেখা যায়:

$$\pi[i] = \max_ {k = 0 \dots i} \{k : s[0 \dots k-1] = s[i-(k-1) \dots i] \}$$

উদাহরণস্বরূপ, “abcabcd” স্ট্রিং-এর প্রিফিক্স ফাংশন হলো $[0, 0, 0, 1, 2, 3, 0]$, এবং “aabaaab” স্ট্রিং-এর প্রিফিক্স ফাংশন হলো $[0, 1, 0, 1, 2, 2, 3]$।

ট্রিভিয়াল অ্যালগরিদম#

প্রিফিক্স ফাংশনের সংজ্ঞা হুবহু অনুসরণ করে এমন অ্যালগরিদম নিম্নরূপ:

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 0; i < n; i++)
        for (int k = 0; k <= i; k++)
            if (s.substr(0, k) == s.substr(i-k+1, k))
                pi[i] = k;
    return pi;
}

দেখা সহজ যে এর কমপ্লেক্সিটি $O(n^3)$, যা উন্নতির সুযোগ রাখে।

দক্ষ অ্যালগরিদম#

এই অ্যালগরিদমটি নুথ এবং প্র্যাট প্রস্তাব করেন এবং তাদের থেকে স্বাধীনভাবে মরিস ১৯৭৭ সালে। এটি একটি সাবস্ট্রিং সার্চ অ্যালগরিদমের মূল ফাংশন হিসেবে ব্যবহৃত হয়েছিল।

প্রথম অপটিমাইজেশন#

প্রথম গুরুত্বপূর্ণ পর্যবেক্ষণ হলো, প্রিফিক্স ফাংশনের মান সর্বাধিক এক বাড়তে পারে।

প্রকৃতপক্ষে, অন্যথায় যদি $\pi[i + 1] \gt \pi[i] + 1$ হয়, তাহলে আমরা $\pi[i + 1]$ দৈর্ঘ্যের $i + 1$ অবস্থানে শেষ হওয়া এই সাফিক্সটি নিতে পারি এবং এর শেষ অক্ষর সরিয়ে দিতে পারি। আমরা $\pi[i + 1] - 1$ দৈর্ঘ্যের $i$ অবস্থানে শেষ হওয়া একটি সাফিক্স পাই, যা $\pi[i]$-এর চেয়ে ভালো, অর্থাৎ আমরা একটি দ্বন্দ্ব পাই।

নিম্নলিখিত চিত্রটি এই দ্বন্দ্ব দেখায়। $i$ অবস্থানে দীর্ঘতম প্রকৃত সাফিক্স যা প্রিফিক্সও তার দৈর্ঘ্য $2$, এবং $i+1$ অবস্থানে এটি $4$। তাই স্ট্রিং $s_0 ~ s_1 ~ s_2 ~ s_3$ স্ট্রিং $s_{i-2} ~ s_{i-1} ~ s_i ~ s_{i+1}$-এর সমান, যার মানে স্ট্রিং $s_0 ~ s_1 ~ s_2$ এবং $s_{i-2} ~ s_{i-1} ~ s_i$-ও সমান, তাই $\pi[i]$ অবশ্যই $3$ হতে হবে।

$$\underbrace{\overbrace{s_0 ~ s_1}^{\pi[i] = 2} ~ s_2 ~ s_3}_{\pi[i+1] = 4} ~ \dots ~ \underbrace{s_{i-2} ~ \overbrace{s_{i-1} ~ s_{i}}^{\pi[i] = 2} ~ s_{i+1}}_{\pi[i+1] = 4}$$

তাই পরবর্তী অবস্থানে যাওয়ার সময়, প্রিফিক্স ফাংশনের মান হয় এক বাড়তে পারে, একই থাকতে পারে, অথবা কিছু পরিমাণ কমতে পারে। এই তথ্যটি ইতিমধ্যে অ্যালগরিদমের কমপ্লেক্সিটি $O(n^2)$-এ কমাতে দেয়, কারণ এক ধাপে প্রিফিক্স ফাংশন সর্বাধিক এক বাড়তে পারে। মোট ফাংশন সর্বাধিক $n$ ধাপ বাড়তে পারে, এবং তাই মোট $n$ ধাপ কমতে পারে। এর মানে আমাদের শুধু $O(n)$ স্ট্রিং তুলনা করতে হবে, এবং $O(n^2)$ কমপ্লেক্সিটিতে পৌঁছাই।

দ্বিতীয় অপটিমাইজেশন#

আরও এগিয়ে যাই, আমরা স্ট্রিং তুলনা থেকে মুক্তি পেতে চাই। এটি করতে, আমাদের পূর্ববর্তী ধাপগুলোতে গণনাকৃত সকল তথ্য ব্যবহার করতে হবে।

তাহলে $i + 1$-এর জন্য প্রিফিক্স ফাংশন $\pi$-এর মান গণনা করি। যদি $s[i+1] = s[\pi[i]]$ হয়, তাহলে আমরা নিশ্চিতভাবে বলতে পারি $\pi[i+1] = \pi[i] + 1$, যেহেতু আমরা ইতিমধ্যে জানি $i$ অবস্থানে $\pi[i]$ দৈর্ঘ্যের সাফিক্স $\pi[i]$ দৈর্ঘ্যের প্রিফিক্সের সমান। এটি আবার একটি উদাহরণ দিয়ে চিত্রিত করা হয়েছে।

$$\underbrace{\overbrace{s_0 ~ s_1 ~ s_2}^{\pi[i]} ~ \overbrace{s_3}^{s_3 = s_{i+1}}}_{\pi[i+1] = \pi[i] + 1} ~ \dots ~ \underbrace{\overbrace{s_{i-2} ~ s_{i-1} ~ s_{i}}^{\pi[i]} ~ \overbrace{s_{i+1}}^{s_3 = s_{i + 1}}}_{\pi[i+1] = \pi[i] + 1}$$

যদি এটি না হয়, $s[i+1] \neq s[\pi[i]]$, তাহলে আমাদের একটি ছোট স্ট্রিং চেষ্টা করতে হবে। গতি বাড়ানোর জন্য, আমরা সরাসরি এমন দীর্ঘতম দৈর্ঘ্য $j \lt \pi[i]$-এ যেতে চাই, যেন $i$ অবস্থানে প্রিফিক্স বৈশিষ্ট্য বজায় থাকে, অর্থাৎ $s[0 \dots j-1] = s[i-j+1 \dots i]$:

$$\overbrace{\underbrace{s_0 ~ s_1}_j ~ s_2 ~ s_3}^{\pi[i]} ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_j}^{\pi[i]} ~ s_{i+1}$$

প্রকৃতপক্ষে, যদি আমরা এরকম দৈর্ঘ্য $j$ পাই, তাহলে আবার শুধু অক্ষর $s[i+1]$ এবং $s[j]$ তুলনা করতে হবে। যদি এরা সমান হয়, তাহলে $\pi[i+1] = j + 1$ অ্যাসাইন করতে পারি। অন্যথায় আমাদের $j$-এর চেয়ে ছোট সবচেয়ে বড় মান খুঁজতে হবে, যার জন্য প্রিফিক্স বৈশিষ্ট্য বজায় থাকে, এবং এভাবে চলতে থাকে। $j = 0$ পর্যন্ত যেতে পারে। তখন যদি $s[i+1] = s[0]$ হয়, আমরা $\pi[i+1] = 1$ অ্যাসাইন করি, এবং অন্যথায় $\pi[i+1] = 0$।

তাই আমাদের কাছে ইতিমধ্যে অ্যালগরিদমের একটি সাধারণ স্কিম আছে। একমাত্র প্রশ্ন হলো কিভাবে দক্ষতার সাথে $j$-এর দৈর্ঘ্যগুলো খুঁজব। সংক্ষেপে: বর্তমান দৈর্ঘ্য $j$-এর জন্য $i$ অবস্থানে প্রিফিক্স বৈশিষ্ট্য বজায় আছে, অর্থাৎ $s[0 \dots j-1] = s[i-j+1 \dots i]$, আমরা সবচেয়ে বড় $k \lt j$ খুঁজতে চাই, যার জন্য প্রিফিক্স বৈশিষ্ট্য বজায় থাকে।

$$\overbrace{\underbrace{s_0 ~ s_1}_k ~ s_2 ~ s_3}^j ~ \dots ~ \overbrace{s_{i-3} ~ s_{i-2} ~ \underbrace{s_{i-1} ~ s_{i}}_k}^j ~s_{i+1}$$

চিত্রটি দেখায় যে, এটি অবশ্যই $\pi[j-1]$-এর মান, যা আমরা আগেই গণনা করেছি।

চূড়ান্ত অ্যালগরিদম#

তাই আমরা শেষ পর্যন্ত এমন একটি অ্যালগরিদম তৈরি করতে পারি যা কোনো স্ট্রিং তুলনা করে না এবং শুধু $O(n)$ কাজ করে।

এখানে চূড়ান্ত পদ্ধতি:

  • আমরা $i = 1$ থেকে $i = n-1$ পর্যন্ত ইটারেট করে লুপে প্রিফিক্স মান $\pi[i]$ গণনা করি ($\pi[0]$-এ কেবল $0$ অ্যাসাইন হয়)।
  • বর্তমান মান $\pi[i]$ গণনা করতে আমরা ভেরিয়েবল $j$ সেট করি যা $i-1$-এর জন্য সেরা সাফিক্সের দৈর্ঘ্য নির্দেশ করে। প্রাথমিকভাবে $j = \pi[i-1]$।
  • পরীক্ষা করি $j+1$ দৈর্ঘ্যের সাফিক্সটিও প্রিফিক্স কিনা, $s[j]$ এবং $s[i]$ তুলনা করে। যদি সমান হয় তাহলে $\pi[i] = j + 1$ অ্যাসাইন করি, অন্যথায় $j$-কে $\pi[j-1]$-এ কমাই এবং এই ধাপ পুনরাবৃত্তি করি।
  • যদি দৈর্ঘ্য $j = 0$-এ পৌঁছাই এবং এখনও মিল না পাই, তাহলে $\pi[i] = 0$ অ্যাসাইন করি এবং পরবর্তী ইনডেক্স $i + 1$-এ যাই।

ইমপ্লিমেন্টেশন#

ইমপ্লিমেন্টেশনটি আশ্চর্যজনকভাবে সংক্ষিপ্ত এবং প্রকাশপূর্ণ।

vector<int> prefix_function(string s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

এটি একটি অনলাইন অ্যালগরিদম, অর্থাৎ এটি ডেটা আসার সাথে সাথে প্রক্রিয়া করে - উদাহরণস্বরূপ, আপনি স্ট্রিং-এর অক্ষরগুলো একটি একটি করে পড়তে পারেন এবং সঙ্গে সঙ্গে প্রক্রিয়া করতে পারেন, প্রতিটি পরবর্তী অক্ষরের জন্য প্রিফিক্স ফাংশনের মান বের করে। অ্যালগরিদমে এখনও স্ট্রিং নিজে এবং প্রিফিক্স ফাংশনের পূর্বে গণনাকৃত মান সংরক্ষণ করতে হবে, কিন্তু যদি আমরা আগে থেকে জানি স্ট্রিং-এ প্রিফিক্স ফাংশন সর্বোচ্চ $M$ মান নিতে পারে, তাহলে আমরা স্ট্রিং-এর শুধু প্রথম $M+1$ অক্ষর এবং একই সংখ্যক প্রিফিক্স ফাংশনের মান সংরক্ষণ করতে পারি।

প্রয়োগ#

একটি স্ট্রিং-এ সাবস্ট্রিং খোঁজা। নুথ-মরিস-প্র্যাট অ্যালগরিদম#

এই কাজটি প্রিফিক্স ফাংশনের ক্লাসিক্যাল প্রয়োগ।

একটি টেক্সট $t$ এবং একটি স্ট্রিং $s$ দেওয়া আছে, আমরা টেক্সট $t$-তে স্ট্রিং $s$-এর সকল অবস্থান খুঁজে বের করতে এবং প্রদর্শন করতে চাই।

সুবিধার জন্য আমরা $n$ দিয়ে স্ট্রিং $s$-এর দৈর্ঘ্য এবং $m$ দিয়ে টেক্সট $t$-এর দৈর্ঘ্য চিহ্নিত করি।

আমরা স্ট্রিং $s + \# + t$ তৈরি করি, যেখানে $\#$ একটি সেপারেটর যা $s$ বা $t$-তে নেই। এই স্ট্রিং-এর জন্য প্রিফিক্স ফাংশন গণনা করি। এখন প্রিফিক্স ফাংশনের মানগুলোর অর্থ ভাবুন, প্রথম $n + 1$ এন্ট্রি ছাড়া (যেগুলো স্ট্রিং $s$ এবং সেপারেটরের)। সংজ্ঞা অনুযায়ী $\pi[i]$ মান $i$ অবস্থানে শেষ হওয়া সাবস্ট্রিং-এর দীর্ঘতম দৈর্ঘ্য দেখায় যা প্রিফিক্সের সাথে মিলে। কিন্তু আমাদের ক্ষেত্রে এটি $s$-এর সাথে মিলে যাওয়া এবং $i$ অবস্থানে শেষ হওয়া সবচেয়ে বড় ব্লক ছাড়া আর কিছু নয়। সেপারেটরের কারণে এই দৈর্ঘ্য $n$-এর চেয়ে বড় হতে পারে না। কিন্তু যদি $\pi[i] = n$ সমতা অর্জিত হয়, তাহলে এর মানে স্ট্রিং $s$ এই অবস্থানে সম্পূর্ণরূপে উপস্থিত, অর্থাৎ এটি $i$ অবস্থানে শেষ হয়। শুধু ভুলবেন না যে অবস্থানগুলো $s + \# + t$ স্ট্রিং-এ ইনডেক্সড।

তাই যদি কোনো অবস্থান $i$-তে $\pi[i] = n$ পাই, তাহলে স্ট্রিং $t$-তে $i - (n + 1) - n + 1 = i - 2n$ অবস্থানে স্ট্রিং $s$ উপস্থিত।

প্রিফিক্স ফাংশন গণনার বর্ণনায় ইতিমধ্যে উল্লেখ করা হয়েছে, যদি আমরা জানি প্রিফিক্সের মান একটি নির্দিষ্ট মান অতিক্রম করবে না, তাহলে পুরো স্ট্রিং এবং পুরো ফাংশন সংরক্ষণ করার দরকার নেই, শুধু এর শুরুটুকু। আমাদের ক্ষেত্রে এর মানে হলো আমাদের শুধু স্ট্রিং $s + \#$ এবং এর প্রিফিক্স ফাংশনের মান সংরক্ষণ করতে হবে। আমরা স্ট্রিং $t$-এর একটি একটি অক্ষর পড়তে পারি এবং প্রিফিক্স ফাংশনের বর্তমান মান গণনা করতে পারি।

এভাবে নুথ-মরিস-প্র্যাট অ্যালগরিদম $O(n + m)$ সময়ে এবং $O(n)$ মেমোরিতে সমস্যাটি সমাধান করে।

প্রতিটি প্রিফিক্সের উপস্থিতির সংখ্যা গণনা#

এখানে আমরা একসাথে দুটি সমস্যা আলোচনা করি। $n$ দৈর্ঘ্যের একটি স্ট্রিং $s$ দেওয়া আছে। প্রথম ভ্যারিয়েশনে আমরা একই স্ট্রিং-এ প্রতিটি প্রিফিক্স $s[0 \dots i]$-এর উপস্থিতির সংখ্যা গণনা করতে চাই। দ্বিতীয় ভ্যারিয়েশনে আরেকটি স্ট্রিং $t$ দেওয়া আছে এবং আমরা $t$-তে প্রতিটি প্রিফিক্স $s[0 \dots i]$-এর উপস্থিতির সংখ্যা গণনা করতে চাই।

প্রথমে প্রথম সমস্যাটি সমাধান করি। $i$ অবস্থানে প্রিফিক্স ফাংশনের মান $\pi[i]$ বিবেচনা করুন। সংজ্ঞা অনুযায়ী এর মানে হলো $\pi[i]$ দৈর্ঘ্যের স্ট্রিং $s$-এর প্রিফিক্স $i$ অবস্থানে ঘটে এবং শেষ হয়, এবং এর চেয়ে দীর্ঘ কোনো প্রিফিক্স এই সংজ্ঞা অনুসরণ করে না। একই সময়ে ছোট প্রিফিক্সগুলো এই অবস্থানে শেষ হতে পারে। দেখা কঠিন নয় যে, আমাদের সেই একই প্রশ্ন আছে যার উত্তর আমরা ইতিমধ্যে দিয়েছি যখন প্রিফিক্স ফাংশন নিজেই গণনা করেছি: $j$ দৈর্ঘ্যের একটি প্রিফিক্স দেওয়া আছে যা $i$ অবস্থানে শেষ হওয়া সাফিক্স, পরবর্তী ছোট প্রিফিক্স $\lt j$ কী যেটিও $i$ অবস্থানে শেষ হওয়া সাফিক্স। তাই $i$ অবস্থানে $\pi[i]$ দৈর্ঘ্যের প্রিফিক্স, $\pi[\pi[i] - 1]$ দৈর্ঘ্যের প্রিফিক্স, $\pi[\pi[\pi[i] - 1] - 1]$ দৈর্ঘ্যের প্রিফিক্স, ইত্যাদি শেষ হয়, যতক্ষণ না ইনডেক্স শূন্য হয়। তাই আমরা নিম্নলিখিতভাবে উত্তর গণনা করতে পারি।

vector<int> ans(n + 1);
for (int i = 0; i < n; i++)
    ans[pi[i]]++;
for (int i = n-1; i > 0; i--)
    ans[pi[i-1]] += ans[i];
for (int i = 0; i <= n; i++)
    ans[i]++;

এখানে প্রিফিক্স ফাংশনের প্রতিটি মানের জন্য আমরা প্রথমে গণনা করি এটি $\pi$ অ্যারেতে কতবার ঘটে, এবং তারপর চূড়ান্ত উত্তর গণনা করি: যদি আমরা জানি $i$ দৈর্ঘ্যের প্রিফিক্স ঠিক $\text{ans}[i]$ বার ঘটে, তাহলে এই সংখ্যাটি এর দীর্ঘতম সাফিক্স যা প্রিফিক্সও তার উপস্থিতির সংখ্যায় যোগ করতে হবে। শেষে প্রতিটি ফলাফলে $1$ যোগ করতে হবে, কারণ মূল প্রিফিক্সগুলোও গণনা করতে হবে।

এখন দ্বিতীয় সমস্যাটি বিবেচনা করি। আমরা নুথ-মরিস-প্র্যাটের কৌশল প্রয়োগ করি: আমরা স্ট্রিং $s + \# + t$ তৈরি করি এবং এর প্রিফিক্স ফাংশন গণনা করি। প্রথম কাজের সাথে একমাত্র পার্থক্য হলো, আমরা শুধু $t$ স্ট্রিং-এর সাথে সম্পর্কিত প্রিফিক্স মানগুলোতে আগ্রহী, অর্থাৎ $i \ge n + 1$-এর জন্য $\pi[i]$। সেই মানগুলো দিয়ে আমরা প্রথম কাজের মতোই হুবহু একই গণনা করতে পারি।

একটি স্ট্রিং-এ ভিন্ন সাবস্ট্রিং-এর সংখ্যা#

$n$ দৈর্ঘ্যের একটি স্ট্রিং $s$ দেওয়া আছে। আমরা এতে উপস্থিত ভিন্ন সাবস্ট্রিং-এর সংখ্যা গণনা করতে চাই।

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

তাই $k$ হলো $s$-তে ভিন্ন সাবস্ট্রিং-এর বর্তমান সংখ্যা, এবং আমরা শেষে $c$ অক্ষর যোগ করি। স্পষ্টতই $c$-তে শেষ হওয়া কিছু নতুন সাবস্ট্রিং উপস্থিত হবে। আমরা এই নতুন সাবস্ট্রিং গণনা করতে চাই যেগুলো আগে ছিল না।

আমরা স্ট্রিং $t = s + c$ নিই এবং এটি বিপরীত করি। এখন কাজটি রূপান্তরিত হয় এমন কতগুলো প্রিফিক্স আছে যা অন্য কোথাও নেই তা গণনায়। যদি আমরা বিপরীত স্ট্রিং $t$-এর প্রিফিক্স ফাংশনের সর্বোচ্চ মান $\pi_{\text{max}}$ গণনা করি, তাহলে $s$-তে উপস্থিত দীর্ঘতম প্রিফিক্সটি $\pi_{\text{max}}$ দীর্ঘ। স্পষ্টতই ছোট দৈর্ঘ্যের সকল প্রিফিক্সও এতে উপস্থিত।

তাই নতুন অক্ষর $c$ যোগ করার সময় নতুন সাবস্ট্রিং-এর সংখ্যা $|s| + 1 - \pi_{\text{max}}$।

তাই প্রতিটি যোগ করা অক্ষরের জন্য আমরা $O(n)$ সময়ে নতুন সাবস্ট্রিং-এর সংখ্যা গণনা করতে পারি, যা মোট $O(n^2)$ টাইম কমপ্লেক্সিটি দেয়।

উল্লেখযোগ্য যে, শুরুতে অক্ষর যোগ করে, অথবা শুরু বা শেষ থেকে অক্ষর মুছেও ভিন্ন সাবস্ট্রিং-এর সংখ্যা গণনা করা যায়।

একটি স্ট্রিং সংকুচিত করা#

$n$ দৈর্ঘ্যের একটি স্ট্রিং $s$ দেওয়া আছে। আমরা স্ট্রিং-এর সংক্ষিপ্ততম “সংকুচিত” উপস্থাপনা খুঁজতে চাই, অর্থাৎ আমরা ক্ষুদ্রতম দৈর্ঘ্যের এমন স্ট্রিং $t$ খুঁজতে চাই যেন $s$-কে $t$-এর এক বা একাধিক কপির সংযুক্তি হিসেবে উপস্থাপন করা যায়।

এটি স্পষ্ট যে, আমাদের শুধু $t$-এর দৈর্ঘ্য খুঁজতে হবে। দৈর্ঘ্য জানা থাকলে, সমস্যার উত্তর হবে এই দৈর্ঘ্যের $s$-এর প্রিফিক্স।

$s$-এর জন্য প্রিফিক্স ফাংশন গণনা করি। এর শেষ মান ব্যবহার করে মান $k = n - \pi[n - 1]$ সংজ্ঞায়িত করি। আমরা দেখাব যে, যদি $k$, $n$-কে ভাগ করে, তাহলে $k$ হবে উত্তর, অন্যথায় কোনো কার্যকর সংকুচন নেই এবং উত্তর হলো $n$।

$n$ যদি $k$ দ্বারা বিভাজ্য হয়। তাহলে স্ট্রিংটি $k$ দৈর্ঘ্যের ব্লকে ভাগ করা যায়। প্রিফিক্স ফাংশনের সংজ্ঞা অনুযায়ী, $n - k$ দৈর্ঘ্যের প্রিফিক্স এর সাফিক্সের সমান। কিন্তু এর মানে শেষ ব্লক আগের ব্লকের সমান। এবং আগের ব্লক তার আগের ব্লকের সমান হতে হবে। ইত্যাদি। ফলে, দেখা যায় সব ব্লক সমান, তাই আমরা স্ট্রিং $s$-কে $k$ দৈর্ঘ্যে সংকুচিত করতে পারি।

অবশ্যই আমাদের এখনও দেখাতে হবে এটি আসলেই অপটিমাম। প্রকৃতপক্ষে, যদি $k$-এর চেয়ে ছোট সংকুচন থাকত, তাহলে শেষে প্রিফিক্স ফাংশনের মান $n - k$-এর চেয়ে বড় হতো। তাই $k$ সত্যিই উত্তর।

এখন ধরি $n$, $k$ দ্বারা বিভাজ্য নয়। আমরা দেখাই যে এর মানে উত্তরের দৈর্ঘ্য $n$। আমরা দ্বন্দ্ব দিয়ে প্রমাণ করি। ধরি একটি উত্তর আছে, এবং সংকুচনের দৈর্ঘ্য $p$ ($p$, $n$-কে ভাগ করে)। তাহলে প্রিফিক্স ফাংশনের শেষ মান $n - p$-এর চেয়ে বড় হতে হবে, অর্থাৎ সাফিক্স আংশিকভাবে প্রথম ব্লক ঢাকবে। এখন স্ট্রিং-এর দ্বিতীয় ব্লক বিবেচনা করুন। যেহেতু প্রিফিক্স সাফিক্সের সমান, এবং প্রিফিক্স ও সাফিক্স উভয়ই এই ব্লক ঢাকে এবং তাদের পরস্পরের সাপেক্ষে সরণ $k$ ব্লক দৈর্ঘ্য $p$ ভাগ করে না (অন্যথায় $k$, $n$ ভাগ করত), তাহলে ব্লকের সব অক্ষর অভিন্ন হতে হবে। কিন্তু তাহলে স্ট্রিংটি শুধু একটি অক্ষরের পুনরাবৃত্তি, ফলে এটি $1$ আকারের স্ট্রিং-এ সংকুচিত হয়, যা $k = 1$ দেয়, এবং $k$, $n$ ভাগ করে। দ্বন্দ্ব।

$$\overbrace{s_0 ~ s_1 ~ s_2 ~ s_3}^p ~ \overbrace{s_4 ~ s_5 ~ s_6 ~ s_7}^p$$$$s_0 ~ s_1 ~ s_2 ~ \underbrace{\overbrace{s_3 ~ s_4 ~ s_5 ~ s_6}^p ~ s_7}_{\pi[7] = 5}$$$$s_4 = s_3, ~ s_5 = s_4, ~ s_6 = s_5, ~ s_7 = s_6 ~ \Rightarrow ~ s_0 = s_1 = s_2 = s_3$$

প্রিফিক্স ফাংশন অনুযায়ী একটি অটোমেটন তৈরি#

আসুন সেপারেটর দিয়ে দুটি স্ট্রিং-এর সংযুক্তিতে ফিরে যাই, অর্থাৎ স্ট্রিং $s$ এবং $t$-এর জন্য আমরা $s + \# + t$ স্ট্রিং-এর প্রিফিক্স ফাংশন গণনা করি। স্পষ্টতই, যেহেতু $\#$ একটি সেপারেটর, প্রিফিক্স ফাংশনের মান কখনো $|s|$-কে অতিক্রম করবে না। এ থেকে বোঝা যায়, শুধু স্ট্রিং $s + \#$ এবং এর প্রিফিক্স ফাংশনের মান সংরক্ষণ করাই যথেষ্ট, এবং আমরা পরবর্তী সকল অক্ষরের জন্য চলমানভাবে প্রিফিক্স ফাংশন গণনা করতে পারি:

$$\underbrace{s_0 ~ s_1 ~ \dots ~ s_{n-1} ~ \#}_{\text{to store}} ~ \underbrace{t_0 ~ t_1 ~ \dots ~ t_{m-1}}_{\text{not to store}}$$

প্রকৃতপক্ষে, এরকম পরিস্থিতিতে পরবর্তী অক্ষর $c \in t$ এবং আগের অবস্থানের প্রিফিক্স ফাংশনের মান জানা থাকলেই পরবর্তী প্রিফিক্স ফাংশনের মান গণনা করার জন্য যথেষ্ট তথ্য থাকে, স্ট্রিং $t$-এর কোনো পূর্ববর্তী অক্ষর বা তাদের প্রিফিক্স ফাংশনের মান ব্যবহার না করেই।

অন্য কথায়, আমরা একটি অটোমেটন (ফিনাইট স্টেট মেশিন) তৈরি করতে পারি: এতে স্টেট হলো প্রিফিক্স ফাংশনের বর্তমান মান, এবং একটি স্টেট থেকে অন্য স্টেটে ট্রানজিশন পরবর্তী অক্ষরের মাধ্যমে হবে।

তাই, স্ট্রিং $t$ ছাড়াই, আমরা এরকম ট্রানজিশন টেবিল $(\text{old}_\pi, c) \rightarrow \text{new}_\pi$ তৈরি করতে পারি, ট্রানজিশন টেবিল গণনার জন্য একই অ্যালগরিদম ব্যবহার করে:

void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            int j = i;
            while (j > 0 && 'a' + c != s[j])
                j = pi[j-1];
            if ('a' + c == s[j])
                j++;
            aut[i][c] = j;
        }
    }
}

তবে এই ফর্মে অ্যালগরিদমটি ছোট হাতের বর্ণমালার জন্য $O(n^2 26)$ সময়ে চলে। লক্ষ্য করুন আমরা ডায়নামিক প্রোগ্রামিং প্রয়োগ করতে পারি এবং টেবিলের ইতিমধ্যে গণনাকৃত অংশ ব্যবহার করতে পারি। যখনই আমরা $j$ মান থেকে $\pi[j-1]$ মানে যাই, আমরা আসলে বলছি ট্রানজিশন $(j, c)$ একই স্টেটে নিয়ে যায় যেটিতে ট্রানজিশন $(\pi[j-1], c)$ নিয়ে যায়, এবং এই উত্তর ইতিমধ্যে সঠিকভাবে গণনা করা হয়েছে।

void compute_automaton(string s, vector<vector<int>>& aut) {
    s += '#';
    int n = s.size();
    vector<int> pi = prefix_function(s);
    aut.assign(n, vector<int>(26));
    for (int i = 0; i < n; i++) {
        for (int c = 0; c < 26; c++) {
            if (i > 0 && 'a' + c != s[i])
                aut[i][c] = aut[pi[i-1]][c];
            else
                aut[i][c] = i + ('a' + c == s[i]);
        }
    }
}

ফলে আমরা $O(26 n)$ সময়ে অটোমেটন তৈরি করি।

এরকম অটোমেটন কখন উপযোগী? শুরুতে মনে রাখুন আমরা স্ট্রিং $s + \# + t$-এর প্রিফিক্স ফাংশন এবং এর মানগুলো বেশিরভাগ ক্ষেত্রে একটি একক উদ্দেশ্যে ব্যবহার করি: স্ট্রিং $t$-তে স্ট্রিং $s$-এর সকল অবস্থান খোঁজা।

তাই এই অটোমেটনের সবচেয়ে স্পষ্ট সুবিধা হলো $s + \# + t$ স্ট্রিং-এর জন্য প্রিফিক্স ফাংশন গণনার ত্বরণ। $s + \#$-এর জন্য অটোমেটন তৈরি করে, আমাদের আর স্ট্রিং $s$ বা এতে প্রিফিক্স ফাংশনের মান সংরক্ষণ করতে হবে না। সকল ট্রানজিশন ইতিমধ্যে টেবিলে গণনা করা হয়েছে।

কিন্তু দ্বিতীয়, কম স্পষ্ট, প্রয়োগও আছে। আমরা অটোমেটন ব্যবহার করতে পারি যখন স্ট্রিং $t$ কোনো নিয়ম অনুসারে তৈরি বিশাল স্ট্রিং হয়। এটি যেমন হতে পারে গ্রে স্ট্রিং, বা ইনপুটের কয়েকটি সংক্ষিপ্ত স্ট্রিং-এর রিকার্সিভ সমন্বয়ে গঠিত স্ট্রিং।

পূর্ণতার জন্য আমরা এরকম একটি সমস্যা সমাধান করব: একটি সংখ্যা $k \le 10^5$ এবং সর্বোচ্চ $\le 10^5$ দৈর্ঘ্যের একটি স্ট্রিং $s$ দেওয়া আছে। আমাদের $k$-তম গ্রে স্ট্রিং-এ $s$-এর উপস্থিতির সংখ্যা গণনা করতে হবে। মনে রাখুন গ্রে-এর স্ট্রিং নিম্নরূপে সংজ্ঞায়িত:

$$\begin{align} g_1 &= \text{"a"}\\ g_2 &= \text{"aba"}\\ g_3 &= \text{"abacaba"}\\ g_4 &= \text{"abacabadabacaba"} \end{align}$$

এরকম ক্ষেত্রে স্ট্রিং $t$ তৈরি করাই অসম্ভব, কারণ এর জ্যোতির্বিদ্যাসুলভ দৈর্ঘ্য। $k$-তম গ্রে স্ট্রিং $2^k-1$ অক্ষর দীর্ঘ। তবে আমরা দক্ষতার সাথে স্ট্রিং-এর শেষে প্রিফিক্স ফাংশনের মান গণনা করতে পারি, শুধু শুরুতে প্রিফিক্স ফাংশনের মান জানা থাকলেই।

অটোমেটন ছাড়াও, আমরা $G[i][j]$ মানও গণনা করি - $j$ স্টেট থেকে শুরু করে $g_i$ স্ট্রিং প্রক্রিয়া করার পরে অটোমেটনের মান। এবং অতিরিক্তভাবে $K[i][j]$ মান গণনা করি - $j$ স্টেট থেকে শুরু করে $g_i$ প্রক্রিয়া করার সময় $s$-এর উপস্থিতির সংখ্যা। আসলে $K[i][j]$ হলো যতবার প্রিফিক্স ফাংশন $|s|$ মান নিয়েছে সেই সংখ্যা। সমস্যার উত্তর হবে $K[k][0]$।

কিভাবে এই মানগুলো গণনা করব? প্রথমে মূল মান হলো $G[0][j] = j$ এবং $K[0][j] = 0$। এবং সকল পরবর্তী মান পূর্ববর্তী মান এবং অটোমেটন ব্যবহার করে গণনা করা যায়। কোনো $i$-এর মান গণনা করতে আমরা মনে রাখি স্ট্রিং $g_i$ গঠিত $g_{i-1}$, বর্ণমালার $i$-তম অক্ষর, এবং $g_{i-1}$ দিয়ে। তাই অটোমেটন স্টেটে যাবে:

$$\text{mid} = \text{aut}[G[i-1][j]][i]$$$$G[i][j] = G[i-1][\text{mid}]$$

$K[i][j]$-এর মানও সহজে গণনা করা যায়।

$$K[i][j] = K[i-1][j] + (\text{mid} == |s|) + K[i-1][\text{mid}]$$

তাই আমরা গ্রে স্ট্রিং-এর সমস্যা সমাধান করতে পারি, এবং একইভাবে অন্যান্য অনেক অনুরূপ সমস্যাও। উদাহরণস্বরূপ একই পদ্ধতি নিম্নলিখিত সমস্যাও সমাধান করে: একটি স্ট্রিং $s$ এবং কিছু প্যাটার্ন $t_i$ দেওয়া আছে, প্রতিটি নিম্নরূপে নির্দিষ্ট: এটি সাধারণ অক্ষরের একটি স্ট্রিং, এবং $t_k^{\text{cnt}}$ আকারে পূর্ববর্তী স্ট্রিং-এর রিকার্সিভ ইনসার্শন থাকতে পারে, যার মানে সেই জায়গায় $t_k$ স্ট্রিং $\text{cnt}$ বার ইনসার্ট হবে। এরকম প্যাটার্নের উদাহরণ:

$$\begin{align} t_1 &= \text{"abdeca"}\\ t_2 &= \text{"abc"} + t_1^{30} + \text{"abd"}\\ t_3 &= t_2^{50} + t_1^{100}\\ t_4 &= t_2^{10} + t_3^{100} \end{align}$$

রিকার্সিভ প্রতিস্থাপন স্ট্রিংকে বিস্ফোরিত করে, তাই তাদের দৈর্ঘ্য $100^{100}$ ক্রমের পর্যন্ত পৌঁছাতে পারে।

আমাদের প্রতিটি স্ট্রিং-এ $s$ কতবার উপস্থিত তা বের করতে হবে।

সমস্যাটি একইভাবে সমাধান করা যায় প্রিফিক্স ফাংশনের অটোমেটন তৈরি করে, এবং তারপর পূর্ববর্তী ফলাফল ব্যবহার করে প্রতিটি প্যাটার্নের ট্রানজিশন গণনা করে।

অনুশীলন সমস্যা#