Fast Fourier Transform#
এই আর্টিকেলে আমরা এমন একটি অ্যালগরিদম আলোচনা করব যা দৈর্ঘ্য $n$-এর দুটি পলিনোমিয়ালকে $O(n \log n)$ সময়ে গুণ করতে দেয়, যা $O(n^2)$ সময়ের ট্রিভিয়াল গুণের চেয়ে ভালো। স্পষ্টতই দুটি বড় সংখ্যার গুণও পলিনোমিয়ালের গুণে রিডিউস করা যায়, তাই দুটি বড় সংখ্যাও $O(n \log n)$ সময়ে গুণ করা যায় (যেখানে $n$ সংখ্যাগুলোর ডিজিটের সংখ্যা)।
Fast Fourier Transformেশন (FFT) আবিষ্কারের কৃতিত্ব কুলি এবং টুকিকে দেওয়া হয়, যারা ১৯৬৫ সালে একটি অ্যালগরিদম প্রকাশ করেন। কিন্তু আসলে FFT এর আগেও বারবার আবিষ্কৃত হয়েছিল, তবে আধুনিক কম্পিউটারের আবিষ্কারের আগে এর গুরুত্ব বোঝা যায়নি। কিছু গবেষক FFT-এর আবিষ্কার ১৯২৪ সালে রুঙ্গে এবং কনিগকে দেন। কিন্তু আসলে গাউস ১৮০৫ সালেই এই পদ্ধতি তৈরি করেছিলেন, তবে কখনো প্রকাশ করেননি।
লক্ষ্য কর, এখানে উপস্থাপিত FFT অ্যালগরিদমটি $O(n \log n)$ সময়ে চলে, কিন্তু এটা ইচ্ছামতো বড় পলিনোমিয়ালের ইচ্ছামতো বড় সহগ সহ অথবা ইচ্ছামতো বড় পূর্ণসংখ্যার গুণের জন্য কাজ করে না। এটা সহজেই $10^5$ আকারের ছোট সহগসহ পলিনোমিয়াল, অথবা $10^6$ আকারের দুটি সংখ্যার গুণ সামলাতে পারে, যা সাধারণত প্রতিযোগিতামূলক প্রোগ্রামিং সমস্যা সমাধানের জন্য যথেষ্ট। $10^6$ বিটের সংখ্যার গুণের স্কেলের বাইরে, গণনায় ব্যবহৃত ফ্লোটিং পয়েন্ট সংখ্যার রেঞ্জ এবং প্রিসিশন সঠিক চূড়ান্ত ফলাফল দিতে যথেষ্ট হবে না, যদিও আরও জটিল ভেরিয়েশন আছে যা ইচ্ছামতো বড় পলিনোমিয়াল/পূর্ণসংখ্যার গুণ করতে পারে। যেমন ১৯৭১ সালে শোনহেগে এবং স্ট্রাসার ইচ্ছামতো বড় সংখ্যার গুণের জন্য একটি ভেরিয়েশন তৈরি করেন যা রিং স্ট্রাকচারে FFT রিকার্সিভভাবে প্রয়োগ করে $O(n \log n \log \log n)$-এ চলে। এবং সম্প্রতি (২০১৯-এ) হার্ভি এবং ভান ডের হুভেন সত্যিকারের $O(n \log n)$-এ চলমান একটি অ্যালগরিদম প্রকাশ করেন।
Discrete Fourier Transform#
ধরি ডিগ্রি $n - 1$-এর একটি পলিনোমিয়াল আছে:
$$A(x) = a_0 x^0 + a_1 x^1 + \dots + a_{n-1} x^{n-1}$$সাধারণতা না হারিয়ে আমরা ধরে নিই $n$ - সহগের সংখ্যা - ২-এর ঘাত। $n$ ২-এর ঘাত না হলে, আমরা কেবল অনুপস্থিত পদ $a_i x^i$ যোগ করি এবং সহগ $a_i$ কে $0$ সেট করি।
জটিল সংখ্যার তত্ত্ব আমাদের বলে যে $x^n = 1$ ইকুয়েশনের $n$ টি জটিল সমাধান আছে ($n$-তম একক মূল বলা হয়), এবং সমাধানগুলো $w_{n, k} = e^{\frac{2 k \pi i}{n}}$ আকারের, $k = 0 \dots n-1$-এর জন্য। এছাড়াও এই জটিল সংখ্যাগুলোর কিছু অত্যন্ত আকর্ষণীয় বৈশিষ্ট্য আছে: যেমন মুখ্য $n$-তম মূল $w_n = w_{n, 1} = e^{\frac{2 \pi i}{n}}$ অন্য সকল $n$-তম মূল বর্ণনা করতে ব্যবহার করা যায়: $w_{n, k} = (w_n)^k$।
পলিনোমিয়াল $A(x)$-এর (বা সমতুল্যভাবে সহগের ভেক্টর $(a_0, a_1, \dots, a_{n-1})$-এর) Discrete Fourier Transform (DFT) ডিফাইন করা হয় $x = w_{n, k}$ বিন্দুগুলোতে পলিনোমিয়ালের মান হিসেবে, অর্থাৎ এটা ভেক্টর:
$$\begin{align} \text{DFT}(a_0, a_1, \dots, a_{n-1}) &= (y_0, y_1, \dots, y_{n-1}) \\ &= (A(w_{n, 0}), A(w_{n, 1}), \dots, A(w_{n, n-1})) \\ &= (A(w_n^0), A(w_n^1), \dots, A(w_n^{n-1})) \end{align}$$একইভাবে ইনভার্স Discrete Fourier Transform ডিফাইন করা হয়: পলিনোমিয়ালের মান $(y_0, y_1, \dots, y_{n-1})$-এর ইনভার্স DFT হলো পলিনোমিয়ালের সহগ $(a_0, a_1, \dots, a_{n-1})$।
$$\text{InverseDFT}(y_0, y_1, \dots, y_{n-1}) = (a_0, a_1, \dots, a_{n-1})$$সুতরাং, যদি একটি ডাইরেক্ট DFT $n$-তম মূলগুলোর বিন্দুতে পলিনোমিয়ালের মান গণনা করে, ইনভার্স DFT সেই মানগুলো ব্যবহার করে পলিনোমিয়ালের সহগ রিকভার করতে পারে।
DFT-এর অ্যাপ্লিকেশন: পলিনোমিয়ালের দ্রুত গুণ#
ধরি দুটি পলিনোমিয়াল $A$ ও $B$ আছে। আমরা প্রতিটির জন্য DFT গণনা করি: $\text{DFT}(A)$ এবং $\text{DFT}(B)$।
এই পলিনোমিয়ালগুলো গুণ করলে কী হয়? স্পষ্টতই প্রতিটি বিন্দুতে মানগুলো কেবল গুণিত হয়, অর্থাৎ
$$(A \cdot B)(x) = A(x) \cdot B(x).$$এর মানে হলো আমরা ভেক্টর $\text{DFT}(A)$ ও $\text{DFT}(B)$ গুণ করলে - একটি ভেক্টরের প্রতিটি এলিমেন্টকে অন্য ভেক্টরের সংশ্লিষ্ট এলিমেন্ট দিয়ে গুণ করলে - পলিনোমিয়াল $\text{DFT}(A \cdot B)$-এর DFT ছাড়া আর কিছুই পাই না:
$$\text{DFT}(A \cdot B) = \text{DFT}(A) \cdot \text{DFT}(B)$$অবশেষে, ইনভার্স DFT প্রয়োগ করে পাই:
$$A \cdot B = \text{InverseDFT}(\text{DFT}(A) \cdot \text{DFT}(B))$$ডানপক্ষে দুই DFT-এর গুণফল দ্বারা আমরা ভেক্টর এলিমেন্টগুলোর জোড়ায় জোড়ায় গুণফল বুঝাচ্ছি। এটা $O(n)$ সময়ে গণনা করা যায়। যদি আমরা DFT এবং ইনভার্স DFT $O(n \log n)$-এ গণনা করতে পারি, তাহলে আমরা একই টাইম কমপ্লেক্সিটিতে দুটি পলিনোমিয়ালের (এবং তাই দুটি বড় সংখ্যার) গুণফল গণনা করতে পারি।
এটা লক্ষ্য করা উচিত যে দুটি পলিনোমিয়ালের একই ডিগ্রি হওয়া উচিত। অন্যথায় DFT-এর দুটি ফলাফল ভেক্টরের ভিন্ন দৈর্ঘ্য হবে। আমরা $0$ মানের সহগ যোগ করে এটা কমপ্লিট করতে পারি।
এবং এছাড়াও, দুটি পলিনোমিয়ালের গুণফল $2 (n - 1)$ ডিগ্রির একটি পলিনোমিয়াল হওয়ায়, আমাদের প্রতিটি পলিনোমিয়ালের ডিগ্রি দ্বিগুণ করতে হবে (আবার $0$ দিয়ে প্যাডিং করে)। $n$ টি মান সহ একটি ভেক্টর থেকে আমরা $2n - 1$ সহগসহ কাঙ্ক্ষিত পলিনোমিয়াল পুনর্গঠন করতে পারি না।
Fast Fourier Transform#
Fast Fourier Transform হলো $O(n \log n)$ সময়ে DFT গণনা করার একটি পদ্ধতি। FFT-এর মূল ধারণা হলো ডিভাইড অ্যান্ড কনকার প্রয়োগ করা। আমরা পলিনোমিয়ালের সহগ ভেক্টরকে দুটি ভেক্টরে ভাগ করি, প্রতিটির জন্য রিকার্সিভভাবে DFT গণনা করি, এবং সম্পূর্ণ পলিনোমিয়ালের DFT গণনা করতে ফলাফলগুলো একত্রিত করি।
তাহলে ধরি ডিগ্রি $n - 1$-এর একটি পলিনোমিয়াল $A(x)$ আছে, যেখানে $n$ ২-এর ঘাত, এবং $n > 1$:
$$A(x) = a_0 x^0 + a_1 x^1 + \dots + a_{n-1} x^{n-1}$$আমরা এটিকে দুটি ছোট পলিনোমিয়ালে ভাগ করি, একটিতে জোড় পজিশনের সহগ এবং অন্যটিতে বিজোড় পজিশনের সহগ:
$$\begin{align} A_0(x) &= a_0 x^0 + a_2 x^1 + \dots + a_{n-2} x^{\frac{n}{2}-1} \\ A_1(x) &= a_1 x^0 + a_3 x^1 + \dots + a_{n-1} x^{\frac{n}{2}-1} \end{align}$$দেখা সহজ যে
$$A(x) = A_0(x^2) + x A_1(x^2).$$পলিনোমিয়াল $A_0$ ও $A_1$-এ $A$-এর সহগের অর্ধেক আছে। যদি আমরা $\text{DFT}(A_0)$ ও $\text{DFT}(A_1)$ ব্যবহার করে রৈখিক সময়ে $\text{DFT}(A)$ গণনা করতে পারি, তাহলে আমরা টাইম কমপ্লেক্সিটির জন্য রিকারেন্স $T_{\text{DFT}}(n) = 2 T_{\text{DFT}}\left(\frac{n}{2}\right) + O(n)$ পাই, যার ফলাফল মাস্টার থিওরেম দ্বারা $T_{\text{DFT}}(n) = O(n \log n)$।
চলো দেখি কীভাবে আমরা এটা কমপ্লিট করতে পারি।
ধরো আমরা ভেক্টর $\left(y_k^0\right)_{k=0}^{n/2-1} = \text{DFT}(A_0)$ এবং $\left(y_k^1\right)_{k=0}^{n/2-1} = \text{DFT}(A_1)$ গণনা করেছি। চলো $\left(y_k\right)_{k=0}^{n-1} = \text{DFT}(A)$-এর জন্য একটি রাশি খুঁজি।
প্রথম $\frac{n}{2}$ মানের জন্য আমরা কেবল আগে উল্লেখিত ইকুয়েশন $A(x) = A_0(x^2) + x A_1(x^2)$ ব্যবহার করতে পারি:
$$y_k = y_k^0 + w_n^k y_k^1, \quad k = 0 \dots \frac{n}{2} - 1.$$তবে দ্বিতীয় $\frac{n}{2}$ মানের জন্য আমাদের একটু ভিন্ন রাশি খুঁজতে হবে:
$$\begin{align} y_{k+n/2} &= A\left(w_n^{k+n/2}\right) \\ &= A_0\left(w_n^{2k+n}\right) + w_n^{k + n/2} A_1\left(w_n^{2k+n}\right) \\ &= A_0\left(w_n^{2k} w_n^n\right) + w_n^k w_n^{n/2} A_1\left(w_n^{2k} w_n^n\right) \\ &= A_0\left(w_n^{2k}\right) - w_n^k A_1\left(w_n^{2k}\right) \\ &= y_k^0 - w_n^k y_k^1 \end{align}$$এখানে আমরা আবার $A(x) = A_0(x^2) + x A_1(x^2)$ এবং দুটি আইডেন্টিটি $w_n^n = 1$ ও $w_n^{n/2} = -1$ ব্যবহার করেছি।
তাই আমরা সম্পূর্ণ ভেক্টর $(y_k)$ গণনার কাঙ্ক্ষিত সূত্রগুলো পাই:
$$\begin{align} y_k &= y_k^0 + w_n^k y_k^1, &\quad k = 0 \dots \frac{n}{2} - 1, \\ y_{k+n/2} &= y_k^0 - w_n^k y_k^1, &\quad k = 0 \dots \frac{n}{2} - 1. \end{align}$$($a + b$ ও $a - b$-এর এই প্যাটার্নকে কখনো কখনো বাটারফ্লাই বলা হয়।)
এভাবে আমরা $O(n \log n)$ সময়ে DFT গণনা করতে শিখলাম।
ইনভার্স FFT#
ধরি ভেক্টর $(y_0, y_1, \dots y_{n-1})$ - ডিগ্রি $n - 1$-এর পলিনোমিয়াল $A$-এর $x = w_n^k$ বিন্দুগুলোতে মান - দেওয়া আছে। আমরা পলিনোমিয়ালের সহগ $(a_0, a_1, \dots, a_{n-1})$ রিকভার করতে চাই। এই পরিচিত সমস্যাটিকে ইন্টারপোলেশন বলা হয়, এবং এটা সমাধানের জন্য সাধারণ অ্যালগরিদম আছে। তবে এই বিশেষ ক্ষেত্রে (যেহেতু আমরা একক মূলগুলোর বিন্দুতে মান জানি), আমরা অনেক সরল একটি অ্যালগরিদম পাই (যা ব্যবহারিকভাবে ডাইরেক্ট FFT-এর মতোই)।
আমরা DFT কে, এর সংজ্ঞা অনুসারে, ম্যাট্রিক্স আকারে লিখতে পারি:
$$ \begin{pmatrix} w_n^0 & w_n^0 & w_n^0 & w_n^0 & \cdots & w_n^0 \\ w_n^0 & w_n^1 & w_n^2 & w_n^3 & \cdots & w_n^{n-1} \\ w_n^0 & w_n^2 & w_n^4 & w_n^6 & \cdots & w_n^{2(n-1)} \\ w_n^0 & w_n^3 & w_n^6 & w_n^9 & \cdots & w_n^{3(n-1)} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ w_n^0 & w_n^{n-1} & w_n^{2(n-1)} & w_n^{3(n-1)} & \cdots & w_n^{(n-1)(n-1)} \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_{n-1} \end{pmatrix} = \begin{pmatrix} y_0 \\ y_1 \\ y_2 \\ y_3 \\ \vdots \\ y_{n-1} \end{pmatrix} $$এই ম্যাট্রিক্সকে ভান্ডেরমন্ড ম্যাট্রিক্স বলা হয়।
সুতরাং আমরা ম্যাট্রিক্সের ইনভার্স দ্বারা বাঁ থেকে ভেক্টর $(y_0, y_1, \dots y_{n-1})$ কে গুণ করে ভেক্টর $(a_0, a_1, \dots, a_{n-1})$ গণনা করতে পারি:
$$ \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_{n-1} \end{pmatrix} = \begin{pmatrix} w_n^0 & w_n^0 & w_n^0 & w_n^0 & \cdots & w_n^0 \\ w_n^0 & w_n^1 & w_n^2 & w_n^3 & \cdots & w_n^{n-1} \\ w_n^0 & w_n^2 & w_n^4 & w_n^6 & \cdots & w_n^{2(n-1)} \\ w_n^0 & w_n^3 & w_n^6 & w_n^9 & \cdots & w_n^{3(n-1)} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ w_n^0 & w_n^{n-1} & w_n^{2(n-1)} & w_n^{3(n-1)} & \cdots & w_n^{(n-1)(n-1)} \end{pmatrix}^{-1} \begin{pmatrix} y_0 \\ y_1 \\ y_2 \\ y_3 \\ \vdots \\ y_{n-1} \end{pmatrix} $$দ্রুত যাচাই করে দেখা যায় ম্যাট্রিক্সের ইনভার্স নিচের আকারের:
$$ \frac{1}{n} \begin{pmatrix} w_n^0 & w_n^0 & w_n^0 & w_n^0 & \cdots & w_n^0 \\ w_n^0 & w_n^{-1} & w_n^{-2} & w_n^{-3} & \cdots & w_n^{-(n-1)} \\ w_n^0 & w_n^{-2} & w_n^{-4} & w_n^{-6} & \cdots & w_n^{-2(n-1)} \\ w_n^0 & w_n^{-3} & w_n^{-6} & w_n^{-9} & \cdots & w_n^{-3(n-1)} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ w_n^0 & w_n^{-(n-1)} & w_n^{-2(n-1)} & w_n^{-3(n-1)} & \cdots & w_n^{-(n-1)(n-1)} \end{pmatrix} $$সুতরাং আমরা সূত্র পাই:
$$a_k = \frac{1}{n} \sum_{j=0}^{n-1} y_j w_n^{-k j}$$$y_k$-এর সূত্রের সাথে তুলনা করলে
$$y_k = \sum_{j=0}^{n-1} a_j w_n^{k j},$$আমরা লক্ষ্য করি যে এই সমস্যাগুলো প্রায় একই, তাই সহগ $a_k$ একই ডিভাইড অ্যান্ড কনকার অ্যালগরিদম দ্বারা, সেইসাথে ডাইরেক্ট FFT দ্বারা পাওয়া যায়, শুধু $w_n^k$-এর পরিবর্তে $w_n^{-k}$ ব্যবহার করতে হবে, এবং শেষে ফলাফলের সহগগুলোকে $n$ দ্বারা ভাগ করতে হবে।
সুতরাং ইনভার্স DFT-এর গণনা ডাইরেক্ট DFT-এর গণনার প্রায় একই, এবং এটিও $O(n \log n)$ সময়ে করা যায়।
ইমপ্লিমেন্টেশন#
এখানে আমরা FFT এবং ইনভার্স FFT-এর একটি সরল রিকার্সিভ ইমপ্লিমেন্টেশন উপস্থাপন করি, উভয় একটি ফাংশনে, কারণ ফরওয়ার্ড ও ইনভার্স FFT-এর পার্থক্য এতটাই সামান্য। জটিল সংখ্যা সংরক্ষণের জন্য আমরা C++ STL-এর complex টাইপ ব্যবহার করি।
using cd = complex<double>;
const double PI = acos(-1);
void fft(vector<cd> & a, bool invert) {
int n = a.size();
if (n == 1)
return;
vector<cd> a0(n / 2), a1(n / 2);
for (int i = 0; 2 * i < n; i++) {
a0[i] = a[2*i];
a1[i] = a[2*i+1];
}
fft(a0, invert);
fft(a1, invert);
double ang = 2 * PI / n * (invert ? -1 : 1);
cd w(1), wn(cos(ang), sin(ang));
for (int i = 0; 2 * i < n; i++) {
a[i] = a0[i] + w * a1[i];
a[i + n/2] = a0[i] - w * a1[i];
if (invert) {
a[i] /= 2;
a[i + n/2] /= 2;
}
w *= wn;
}
}ফাংশনটি সহগের একটি ভেক্টর পাস করে, এবং ফাংশন DFT অথবা ইনভার্স DFT গণনা করে ফলাফল আবার এই ভেক্টরে সংরক্ষণ করে। $\text{invert}$ আর্গুমেন্ট দেখায় ডাইরেক্ট না ইনভার্স DFT গণনা করা উচিত। ফাংশনের ভেতরে আমরা প্রথমে পরীক্ষা করি ভেক্টরের দৈর্ঘ্য এক কিনা, তাহলে কিছু করার দরকার নেই। অন্যথায় আমরা ভেক্টর $a$ কে দুটি ভেক্টর $a0$ ও $a1$-এ ভাগ করি এবং উভয়ের জন্য রিকার্সিভভাবে DFT গণনা করি। তারপর আমরা $wn$ মান এবং একটি ভেরিয়েবল $w$ ইনিশিয়ালাইজ করি, যেটিতে $wn$-এর বর্তমান ঘাত থাকবে। তারপর উপরের সূত্র ব্যবহার করে ফলাফল DFT-এর মান গণনা করা হয়।
$\text{invert}$ ফ্ল্যাগ সেট থাকলে, আমরা $wn$ কে $wn^{-1}$ দিয়ে প্রতিস্থাপন করি, এবং ফলাফলের প্রতিটি মান $2$ দ্বারা ভাগ করি (যেহেতু এটা রিকার্সনের প্রতিটি স্তরে করা হবে, এটা শেষ পর্যন্ত চূড়ান্ত মানগুলোকে $n$ দ্বারা ভাগ করবে)।
এই ফাংশন ব্যবহার করে আমরা দুটি পলিনোমিয়াল গুণ করার একটি ফাংশন তৈরি করতে পারি:
vector<int> multiply(vector<int> const& a, vector<int> const& b) {
vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
int n = 1;
while (n < a.size() + b.size())
n <<= 1;
fa.resize(n);
fb.resize(n);
fft(fa, false);
fft(fb, false);
for (int i = 0; i < n; i++)
fa[i] *= fb[i];
fft(fa, true);
vector<int> result(n);
for (int i = 0; i < n; i++)
result[i] = round(fa[i].real());
return result;
}এই ফাংশন ইন্টিজার সহগসহ পলিনোমিয়ালের সাথে কাজ করে, তবে তুমি এটা অন্য টাইপের সাথে কাজ করতেও সামঞ্জস্য করতে পারেন। যেহেতু জটিল সংখ্যার সাথে কাজ করলে কিছু ত্রুটি হয়, শেষে ফলাফলের সহগগুলো রাউন্ড করতে হবে।
অবশেষে দুটি বড় সংখ্যা গুণ করার ফাংশন ব্যবহারিকভাবে পলিনোমিয়াল গুণের ফাংশন থেকে আলাদা নয়। শুধু পরে সংখ্যাটি নরমালাইজ করতে হবে:
int carry = 0;
for (int i = 0; i < n; i++)
result[i] += carry;
carry = result[i] / 10;
result[i] %= 10;
}দুটি সংখ্যার গুণফলের দৈর্ঘ্য কখনো উভয় সংখ্যার মোট দৈর্ঘ্য অতিক্রম না করায়, ভেক্টরের আকার সকল ক্যারি অপারেশন সম্পাদনের জন্য যথেষ্ট।
উন্নত ইমপ্লিমেন্টেশন: ইন-প্লেস গণনা#
দক্ষতা বাড়াতে আমরা রিকার্সিভ ইমপ্লিমেন্টেশন থেকে ইটারেটিভে স্যুইচ করব। উপরের রিকার্সিভ ইমপ্লিমেন্টেশনে আমরা সুস্পষ্টভাবে ভেক্টর $a$ কে দুটি ভেক্টরে আলাদা করেছি - জোড় পজিশনের এলিমেন্ট একটি অস্থায়ী ভেক্টরে, এবং বিজোড় পজিশনের এলিমেন্ট আরেকটিতে। তবে আমরা যদি এলিমেন্টগুলোকে একটি নির্দিষ্ট উপায়ে পুনর্বিন্যাস করি, আমাদের এই অস্থায়ী ভেক্টর তৈরি করার দরকার নেই (অর্থাৎ সকল গণনা “ইন-প্লেস”, ভেক্টর $A$-তেই করা যায়)।
লক্ষ্য কর প্রথম রিকার্সন লেভেলে, পজিশনের সর্বনিম্ন বিট শূন্য হলে এলিমেন্ট $a_0$ ভেক্টরে এবং সর্বনিম্ন বিট এক হলে $a_1$ ভেক্টরে বরাদ্দ হয়। দ্বিতীয় রিকার্সন লেভেলে একই ঘটনা ঘটে, তবে দ্বিতীয় সর্বনিম্ন বিট দিয়ে, ইত্যাদি। তাই আমরা যদি প্রতিটি সহগের পজিশনের বিটগুলো উল্টে দিই, এবং এই উল্টানো মান দ্বারা সর্ট করি, আমরা কাঙ্ক্ষিত ক্রম পাই (এটিকে বিট-রিভার্সাল পারমুটেশন বলা হয়)।
উদাহরণস্বরূপ $n = 8$-এর জন্য কাঙ্ক্ষিত ক্রম হলো:
$$a = \bigg\{ \Big[ (a_0, a_4), (a_2, a_6) \Big], \Big[ (a_1, a_5), (a_3, a_7) \Big] \bigg\}$$আসলে প্রথম রিকার্সন লেভেলে (কার্লি ব্রেসের মধ্যে), ভেক্টরটি দুই ভাগে বিভক্ত হয় $[a_0, a_2, a_4, a_6]$ এবং $[a_1, a_3, a_5, a_7]$। দেখা যায়, বিট-রিভার্সাল পারমুটেশনে এটা কেবল ভেক্টরকে দুই ভাগে ভাগ করার সমতুল্য: প্রথম $\frac{n}{2}$ এলিমেন্ট এবং শেষ $\frac{n}{2}$ এলিমেন্ট। তারপর প্রতিটি অর্ধেকের জন্য একটি রিকার্সিভ কল হয়। ধরি তাদের প্রতিটির জন্য ফলাফল DFT এলিমেন্টগুলোর স্থানেই রিটার্ন করা হয় (অর্থাৎ ভেক্টর $a$-এর প্রথম অর্ধেক এবং দ্বিতীয় অর্ধেক যথাক্রমে)।
$$a = \bigg\{ \Big[y_0^0, y_1^0, y_2^0, y_3^0\Big], \Big[y_0^1, y_1^1, y_2^1, y_3^1 \Big] \bigg\}$$এখন আমরা দুটি DFT কে সম্পূর্ণ ভেক্টরের জন্য একটিতে একত্রিত করতে চাই। এলিমেন্টগুলোর ক্রম আদর্শ, এবং আমরা সরাসরি এই ভেক্টরেই ইউনিয়ন করতে পারি। আমরা $y_0^0$ ও $y_0^1$ এলিমেন্ট নিয়ে বাটারফ্লাই ট্রান্সফর্ম করতে পারি। ফলাফলের দুটি মানের স্থান দুটি প্রাথমিক মানের স্থানের মতোই, তাই আমরা পাই:
$$a = \bigg\{ \Big[y_0^0 + w_n^0 y_0^1, y_1^0, y_2^0, y_3^0\Big], \Big[y_0^0 - w_n^0 y_0^1, y_1^1, y_2^1, y_3^1\Big] \bigg\}$$একইভাবে আমরা $y_1^0$ ও $y_1^1$-এর বাটারফ্লাই ট্রান্সফর্ম গণনা করতে পারি এবং ফলাফল তাদের স্থানে রাখতে পারি, ইত্যাদি। তাই আমরা পাই:
$$a = \bigg\{ \Big[y_0^0 + w_n^0 y_0^1, y_1^0 + w_n^1 y_1^1, y_2^0 + w_n^2 y_2^1, y_3^0 + w_n^3 y_3^1\Big], \Big[y_0^0 - w_n^0 y_0^1, y_1^0 - w_n^1 y_1^1, y_2^0 - w_n^2 y_2^1, y_3^0 - w_n^3 y_3^1\Big] \bigg\}$$এভাবে আমরা ভেক্টর $a$ থেকে প্রয়োজনীয় DFT গণনা করলাম।
এখানে আমরা শুধু প্রথম রিকার্সন লেভেলে DFT গণনার প্রক্রিয়া বর্ণনা করেছি, তবে একই পদ্ধতি স্পষ্টতই অন্য সকল লেভেলেও কাজ করে। সুতরাং, বিট-রিভার্সাল পারমুটেশন প্রয়োগের পর, আমরা কোনো অতিরিক্ত মেমোরি ছাড়াই ইন-প্লেসে DFT গণনা করতে পারি।
এটা অতিরিক্তভাবে রিকার্সন থেকে মুক্তি পেতে দেয়। আমরা সর্বনিম্ন স্তর থেকে শুরু করি, অর্থাৎ ভেক্টরকে জোড়ায় ভাগ করি এবং তাদের উপর বাটারফ্লাই ট্রান্সফর্ম প্রয়োগ করি। এতে শেষ স্তরের কাজ প্রয়োগ করা ভেক্টর $a$ পাওয়া যায়। পরবর্তী ধাপে আমরা ভেক্টরকে ৪ আকারের ভেক্টরে ভাগ করি, এবং আবার বাটারফ্লাই ট্রান্সফর্ম প্রয়োগ করি, যা ৪ আকারের প্রতিটি ব্লকের জন্য DFT দেয়। এবং এভাবে চলতে থাকে। অবশেষে শেষ ধাপে আমরা $a$-এর উভয় অর্ধেকের DFT-এর ফলাফল পাই, এবং বাটারফ্লাই ট্রান্সফর্ম প্রয়োগ করে সম্পূর্ণ ভেক্টর $a$-এর DFT পাই।
using cd = complex<double>;
const double PI = acos(-1);
int reverse(int num, int lg_n) {
int res = 0;
for (int i = 0; i < lg_n; i++) {
if (num & (1 << i))
res |= 1 << (lg_n - 1 - i);
}
return res;
}
void fft(vector<cd> & a, bool invert) {
int n = a.size();
int lg_n = 0;
while ((1 << lg_n) < n)
lg_n++;
for (int i = 0; i < n; i++) {
if (i < reverse(i, lg_n))
swap(a[i], a[reverse(i, lg_n)]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (invert ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int j = 0; j < len / 2; j++) {
cd u = a[i+j], v = a[i+j+len/2] * w;
a[i+j] = u + v;
a[i+j+len/2] = u - v;
w *= wlen;
}
}
}
if (invert) {
for (cd & x : a)
x /= n;
}
}প্রথমে আমরা প্রতিটি এলিমেন্টকে উল্টানো পজিশনের এলিমেন্টের সাথে অদলবদল করে বিট-রিভার্সাল পারমুটেশন প্রয়োগ করি। তারপর $\log n - 1$ ধাপে আমরা সংশ্লিষ্ট $\text{len}$ আকারের প্রতিটি ব্লকের জন্য DFT গণনা করি। সেই সকল ব্লকের জন্য আমাদের একই একক মূল $\text{wlen}$ আছে। আমরা সকল ব্লকের মধ্য দিয়ে ইটারেট করি এবং তাদের প্রতিটিতে বাটারফ্লাই ট্রান্সফর্ম করি।
আমরা বিটের রিভার্সালটি আরও অপটিমাইজ করতে পারি। আগের ইমপ্লিমেন্টেশনে আমরা ইনডেক্সের সকল বিট ইটারেট করে বিটওয়াইজ উল্টানো ইনডেক্স তৈরি করেছি। তবে আমরা ভিন্নভাবে বিট উল্টাতে পারি।
ধরো $j$-তে ইতিমধ্যে $i$-এর রিভার্স আছে। তাহলে $i + 1$-এ যেতে, আমাদের $i$ ইনক্রিমেন্ট করতে হবে, এবং $j$ ও ইনক্রিমেন্ট করতে হবে, তবে “উল্টানো” সংখ্যা পদ্ধতিতে। প্রচলিত বাইনারি পদ্ধতিতে এক যোগ করার অর্থ হলো সকল ট্রেইলিং ওয়ান শূন্যে ফ্লিপ করা এবং তার ঠিক আগের শূন্যকে একে ফ্লিপ করা। সমতুল্যভাবে “উল্টানো” সংখ্যা পদ্ধতিতে, আমরা সকল লিডিং ওয়ান ফ্লিপ করি, এবং পরবর্তী শূন্যও ফ্লিপ করি।
সুতরাং আমরা নিচের ইমপ্লিমেন্টেশন পাই:
using cd = complex<double>;
const double PI = acos(-1);
void fft(vector<cd> & a, bool invert) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1)
j ^= bit;
j ^= bit;
if (i < j)
swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
double ang = 2 * PI / len * (invert ? -1 : 1);
cd wlen(cos(ang), sin(ang));
for (int i = 0; i < n; i += len) {
cd w(1);
for (int j = 0; j < len / 2; j++) {
cd u = a[i+j], v = a[i+j+len/2] * w;
a[i+j] = u + v;
a[i+j+len/2] = u - v;
w *= wlen;
}
}
}
if (invert) {
for (cd & x : a)
x /= n;
}
}এছাড়াও আমরা বিট-রিভার্সাল পারমুটেশন আগে থেকে প্রিকম্পিউট করতে পারি। এটা বিশেষভাবে উপকারী যখন আকার $n$ সকল কলের জন্য একই। তবে যখন আমাদের শুধু তিনটি কল আছে (যেগুলো দুটি পলিনোমিয়াল গুণ করতে প্রয়োজন), প্রভাবটি লক্ষণীয়। এছাড়াও আমরা সকল একক মূল এবং তাদের ঘাত প্রিকম্পিউট করতে পারি।
Number Theoretic Transform (NTT)#
এখন আমরা উদ্দেশ্যটি একটু পরিবর্তন করি। আমরা এখনো দুটি পলিনোমিয়াল $O(n \log n)$ সময়ে গুণ করতে চাই, তবে এবার আমরা কোনো মৌলিক সংখ্যা $p$ মডুলোতে সহগ গণনা করতে চাই। অবশ্যই এই কাজের জন্য আমরা স্বাভাবিক DFT ব্যবহার করে ফলাফলে মডুলো অপারেটর প্রয়োগ করতে পারি। তবে, এটা করলে রাউন্ডিং ত্রুটি হতে পারে, বিশেষ করে বড় সংখ্যার ক্ষেত্রে। NTT-এর সুবিধা হলো, এটা শুধুমাত্র পূর্ণসংখ্যার সাথে কাজ করে, এবং তাই ফলাফল সঠিক হওয়ার গ্যারান্টি দেওয়া হয়।
Discrete Fourier Transform জটিল সংখ্যার উপর ভিত্তি করে, এবং $n$-তম একক মূলের উপর। এটা দক্ষভাবে গণনা করতে, আমরা মূলগুলোর বৈশিষ্ট্যগুলো ব্যাপকভাবে ব্যবহার করি (যেমন একটি মূল আছে যা সূচকীকরণের মাধ্যমে অন্য সকল মূল তৈরি করে)।
তবে মডুলার অ্যারিথমেটিকে $n$-তম একক মূলের জন্যও একই বৈশিষ্ট্যগুলো ধরে রাখে। একটি প্রিমিটিভ ফিল্ডে $n$-তম একক মূল হলো এমন একটি সংখ্যা $w_n$ যা পূরণ করে:
$$\begin{align} (w_n)^n &= 1 \pmod{p}, \\ (w_n)^k &\ne 1 \pmod{p}, \quad 1 \le k < n. \end{align}$$অন্য $n-1$ টি মূল $w_n$-এর ঘাত হিসেবে পাওয়া যায়।
Fast Fourier Transform অ্যালগরিদমে এটা প্রয়োগ করতে, আমাদের কোনো $n$-এর জন্য একটি মূল থাকা দরকার, যেটা ২-এর ঘাত, এবং সকল ছোট ঘাতের জন্যও। আমরা নিচের আকর্ষণীয় বৈশিষ্ট্যটি লক্ষ্য করতে পারি:
$$\begin{align} (w_n^2)^m = w_n^n &= 1 \pmod{p}, \quad \text{with } m = \frac{n}{2}\\ (w_n^2)^k = w_n^{2k} &\ne 1 \pmod{p}, \quad 1 \le k < m. \end{align}$$সুতরাং $w_n$ যদি $n$-তম একক মূল হয়, তাহলে $w_n^2$ হলো $\frac{n}{2}$-তম একক মূল। এবং তাই ২-এর সকল ছোট ঘাতের জন্য প্রয়োজনীয় ডিগ্রির মূল আছে, এবং $w_n$ ব্যবহার করে সেগুলো গণনা করা যায়।
ইনভার্স DFT গণনার জন্য, আমাদের $w_n$-এর ইনভার্স $w_n^{-1}$ দরকার। তবে একটি মৌলিক মডুলাসের জন্য ইনভার্স সর্বদা বিদ্যমান।
সুতরাং জটিল মূলগুলো থেকে আমাদের যেসব বৈশিষ্ট্য দরকার সেগুলো মডুলার অ্যারিথমেটিকেও পাওয়া যায়, যদি আমাদের কাছে যথেষ্ট বড় মডুল $p$ থাকে যার জন্য $n$-তম একক মূল বিদ্যমান।
উদাহরণস্বরূপ আমরা নিচের মান নিতে পারি: মডুল $p = 7340033$, $w_{2^{20}} = 5$। এই মডুল যথেষ্ট না হলে, আমাদের ভিন্ন জোড়া খুঁজতে হবে। আমরা এই তথ্য ব্যবহার করতে পারি যে $p = c 2^k + 1$ আকারের মডুলগুলোর জন্য (এবং $p$ মৌলিক হলে), সর্বদা $2^k$-তম একক মূল বিদ্যমান। দেখানো যায় যে $g^c$ একটি $2^k$-তম একক মূল, যেখানে $g$ হলো $p$-এর একটি প্রিমিটিভ রুট।
const int mod = 7340033;
const int root = 5;
const int root_1 = 4404020;
const int root_pw = 1 << 20;
void fft(vector<int> & a, bool invert) {
int n = a.size();
for (int i = 1, j = 0; i < n; i++) {
int bit = n >> 1;
for (; j & bit; bit >>= 1)
j ^= bit;
j ^= bit;
if (i < j)
swap(a[i], a[j]);
}
for (int len = 2; len <= n; len <<= 1) {
int wlen = invert ? root_1 : root;
for (int i = len; i < root_pw; i <<= 1)
wlen = (int)(1LL * wlen * wlen % mod);
for (int i = 0; i < n; i += len) {
int w = 1;
for (int j = 0; j < len / 2; j++) {
int u = a[i+j], v = (int)(1LL * a[i+j+len/2] * w % mod);
a[i+j] = u + v < mod ? u + v : u + v - mod;
a[i+j+len/2] = u - v >= 0 ? u - v : u - v + mod;
w = (int)(1LL * w * wlen % mod);
}
}
}
if (invert) {
int n_1 = inverse(n, mod);
for (int & x : a)
x = (int)(1LL * x * n_1 % mod);
}
}এখানে inverse ফাংশনটি মডুলার ইনভার্স গণনা করে (মডুলার মাল্টিপ্লিকেটিভ ইনভার্স দেখো)।
ধ্রুবকগুলো mod, root, root_pw মডুল এবং মূল ডিটারমিন করে, এবং root_1 হলো mod মডুলোতে root-এর ইনভার্স।
প্র্যাকটিসে এই ইমপ্লিমেন্টেশন জটিল সংখ্যা ব্যবহার করা ইমপ্লিমেন্টেশনের চেয়ে ধীর (বিশাল সংখ্যক মডুলো অপারেশনের কারণে), তবে কম মেমোরি ব্যবহার এবং কোনো রাউন্ডিং ত্রুটি না থাকার মতো কিছু সুবিধা আছে।
ইচ্ছামতো মডুলাস সহ গুণ#
এখানে আমরা আগের অনুচ্ছেদের মতোই লক্ষ্য অর্জন করতে চাই। দুটি পলিনোমিয়াল $A(x)$ ও $B(x)$ গুণ করা, এবং সহগ কোনো সংখ্যা $M$ মডুলোতে গণনা করা। NTT শুধুমাত্র নির্দিষ্ট মৌলিক সংখ্যার জন্য কাজ করে। মডুলাস কাঙ্ক্ষিত আকারের না হলে কী হবে?
একটি বিকল্প হলো $c 2^k + 1$ আকারের ভিন্ন মৌলিক সংখ্যা দিয়ে একাধিক NTT করা, তারপর চূড়ান্ত সহগ গণনা করতে চায়নিজ রিমেইন্ডার থিওরেম প্রয়োগ করা।
আরেকটি বিকল্প হলো পলিনোমিয়াল $A(x)$ ও $B(x)$ কে প্রতিটি দুটি ছোট পলিনোমিয়ালে বিতরণ করা
$$\begin{align} A(x) &= A_1(x) + A_2(x) \cdot C \\ B(x) &= B_1(x) + B_2(x) \cdot C \end{align}$$$C \approx \sqrt{M}$ সহ।
তারপর $A(x)$ ও $B(x)$-এর গুণফল এভাবে উপস্থাপন করা যায়:
$$A(x) \cdot B(x) = A_1(x) \cdot B_1(x) + \left(A_1(x) \cdot B_2(x) + A_2(x) \cdot B_1(x)\right)\cdot C + \left(A_2(x) \cdot B_2(x)\right)\cdot C^2$$পলিনোমিয়াল $A_1(x)$, $A_2(x)$, $B_1(x)$ ও $B_2(x)$-এ $\sqrt{M}$-এর চেয়ে ছোট সহগ আছে, তাই সকল প্রদর্শিত গুণফলের সহগ $M \cdot n$-এর চেয়ে ছোট, যা সাধারণত প্রচলিত ফ্লোটিং পয়েন্ট টাইপ দিয়ে সামলানোর মতো যথেষ্ট ছোট।
এই পদ্ধতিতে তাই ছোট সহগসহ পলিনোমিয়ালের গুণফল গণনা করা প্রয়োজন (স্বাভাবিক FFT ও ইনভার্স FFT ব্যবহার করে), এবং তারপর মডুলার যোগ ও গুণ ব্যবহার করে $O(n)$ সময়ে মূল গুণফল রিকভার করা যায়।
অ্যাপ্লিকেশন#
DFT বিভিন্ন ধরনের সমস্যায় ব্যবহার করা যায়, যেগুলো প্রথম দৃষ্টিতে পলিনোমিয়াল গুণের সাথে কোনো সম্পর্ক নেই।
সকল সম্ভাব্য যোগফল#
দুটি অ্যারে $a[]$ ও $b[]$ দেওয়া আছে। আমাদের সকল সম্ভাব্য যোগফল $a[i] + b[j]$ খুঁজতে হবে, এবং প্রতিটি যোগফল কতবার আসে তা গণনা করতে হবে।
উদাহরণস্বরূপ $a = [1,~ 2,~ 3]$ এবং $b = [2,~ 4]$-এর জন্য: যোগফল $3$ ১ ভাবে পাওয়া যায়, যোগফল $4$ও ১ ভাবে, $5$ ২ ভাবে, $6$ ১ ভাবে, $7$ ১ ভাবে।
আমরা অ্যারে $a$ ও $b$-এর জন্য দুটি পলিনোমিয়াল $A$ ও $B$ তৈরি করি। অ্যারের সংখ্যাগুলো পলিনোমিয়ালে সূচক হিসেবে কাজ করবে ($a[i] \Rightarrow x^{a[i]}$); এবং এই পদের সহগ হবে সংখ্যাটি অ্যারেতে কতবার আসে।
তারপর, $O(n \log n)$ সময়ে এই দুটি পলিনোমিয়াল গুণ করে, আমরা একটি পলিনোমিয়াল $C$ পাই, যেখানে সূচকগুলো বলবে কোন যোগফলগুলো পাওয়া সম্ভব, এবং সহগগুলো বলবে কতবার। উদাহরণটিতে দেখানো হলো:
$$(1 x^1 + 1 x^2 + 1 x^3) (1 x^2 + 1 x^4) = 1 x^3 + 1 x^4 + 2 x^5 + 1 x^6 + 1 x^7$$সকল সম্ভাব্য স্কেলার গুণফল#
দৈর্ঘ্য $n$-এর দুটি অ্যারে $a[]$ ও $b[]$ দেওয়া আছে। আমাদের $b$-এর প্রতিটি সাইক্লিক শিফটের সাথে $a$-এর গুণফল গণনা করতে হবে।
আমরা $2n$ আকারের দুটি নতুন অ্যারে তৈরি করি: আমরা $a$ উল্টে দিই এবং $n$ টি শূন্য যোগ করি। এবং আমরা কেবল $b$ কে নিজের সাথে যোগ করি। যখন আমরা এই দুটি অ্যারে পলিনোমিয়াল হিসেবে গুণ করি, এবং গুণফল $c$-এর $c[n-1],~ c[n],~ \dots,~ c[2n-2]$ সহগগুলো দেখি, আমরা পাই:
$$c[k] = \sum_{i+j=k} a[i] b[j]$$এবং যেহেতু $i \ge n$-এর জন্য সকল $a[i] = 0$:
$$c[k] = \sum_{i=0}^{n-1} a[i] b[k-i]$$দেখা সহজ যে এই যোগফলটি কেবল ভেক্টর $a$-এর সাথে $b$-এর $(k - (n - 1))$-তম সাইক্লিক লেফট শিফটের স্কেলার গুণফল। সুতরাং এই সহগগুলোই সমস্যার উত্তর, এবং আমরা এখনও $O(n \log n)$ সময়ে এটা পেতে সক্ষম হয়েছি। এখানে লক্ষ্য কর $c[2n-1]$ও আমাদের $n$-তম সাইক্লিক শিফট দেয় কিন্তু সেটা $0$-তম সাইক্লিক শিফটের মতোই তাই আমাদের এটা আলাদাভাবে উত্তরে কনসিডার করার দরকার নেই।
দুটি স্ট্রিপ#
দুটি বুলিয়ান স্ট্রিপ (মান $0$ ও $1$-এর সাইক্লিক অ্যারে) $a$ ও $b$ দেওয়া আছে। আমরা প্রথম স্ট্রিপটি দ্বিতীয়টির সাথে সংযুক্ত করার সকল উপায় খুঁজতে চাই, যেন কোনো পজিশনে প্রথম স্ট্রিপের $1$ দ্বিতীয় স্ট্রিপের $1$-এর পাশে না থাকে।
সমস্যাটি আগের সমস্যা থেকে খুব বেশি আলাদা নয়। দুটি স্ট্রিপ সংযুক্ত করার মানে হলো আমরা দ্বিতীয় অ্যারেতে সাইক্লিক শিফট করি, এবং দুটি অ্যারের স্কেলার গুণফল $0$ হলে আমরা দুটি স্ট্রিপ সংযুক্ত করতে পারি।
স্ট্রিং ম্যাচিং#
দুটি স্ট্রিং দেওয়া আছে, একটি টেক্সট $T$ এবং একটি প্যাটার্ন $P$, ছোট হাতের অক্ষর দিয়ে গঠিত। আমাদের টেক্সটে প্যাটার্নের সকল অবস্থান গণনা করতে হবে।
আমরা প্রতিটি স্ট্রিংয়ের জন্য একটি পলিনোমিয়াল তৈরি করি ($T[i]$ ও $P[I]$ হলো বর্ণমালার ২৬টি অক্ষরের সাথে সংশ্লিষ্ট $0$ থেকে $25$-এর মধ্যে সংখ্যা):
$$A(x) = a_0 x^0 + a_1 x^1 + \dots + a_{n-1} x^{n-1}, \quad n = |T|$$যেখানে
$$a_i = \cos(\alpha_i) + i \sin(\alpha_i), \quad \alpha_i = \frac{2 \pi T[i]}{26}.$$এবং
$$B(x) = b_0 x^0 + b_1 x^1 + \dots + b_{m-1} x^{m-1}, \quad m = |P|$$যেখানে
$$b_i = \cos(\beta_i) - i \sin(\beta_i), \quad \beta_i = \frac{2 \pi P[m-i-1]}{26}.$$লক্ষ্য কর $P[m-i-1]$ রাশি দিয়ে প্যাটার্নটি সুস্পষ্টভাবে উল্টানো হয়েছে।
দুটি পলিনোমিয়ালের গুণফল $C(x) = A(x) \cdot B(x)$-এর $(m-1+i)$-তম সহগ আমাদের বলবে, প্যাটার্ন টেক্সটে $i$ পজিশনে আছে কিনা।
$$c_{m-1+i} = \sum_{j = 0}^{m-1} a_{i+j} \cdot b_{m-1-j} = \sum_{j=0}^{m-1} \left(\cos(\alpha_{i+j}) + i \sin(\alpha_{i+j})\right) \cdot \left(\cos(\beta_j) - i \sin(\beta_j)\right)$$$\alpha_{i+j} = \frac{2 \pi T[i+j]}{26}$ এবং $\beta_j = \frac{2 \pi P[j]}{26}$ সহ
ম্যাচ থাকলে, $T[i+j] = P[j]$, এবং তাই $\alpha_{i+j} = \beta_j$। এটা দেয় (পিথাগোরীয় ত্রিকোণমিতিক আইডেন্টিটি ব্যবহার করে):
$$\begin{align} c_{m-1+i} &= \sum_{j = 0}^{m-1} \left(\cos(\alpha_{i+j}) + i \sin(\alpha_{i+j})\right) \cdot \left(\cos(\alpha_{i+j}) - i \sin(\alpha_{i+j})\right) \\ &= \sum_{j = 0}^{m-1} \cos(\alpha_{i+j})^2 + \sin(\alpha_{i+j})^2 = \sum_{j = 0}^{m-1} 1 = m \end{align}$$ম্যাচ না থাকলে, অন্তত একটি অক্ষর ভিন্ন, যা বলে যে একটি গুণফল $a_{i+1} \cdot b_{m-1-j}$ $1$-এর সমান নয়, যা সহগ $c_{m-1+i} \ne m$ তে নিয়ে যায়।
ওয়াইল্ডকার্ড সহ স্ট্রিং ম্যাচিং#
এটা আগের সমস্যার একটি সম্প্রসারণ। এবার আমরা অনুমতি দিই যে প্যাটার্নে ওয়াইল্ডকার্ড ক্যারেক্টার $\*$ থাকতে পারে, যা যেকোনো সম্ভাব্য অক্ষরের সাথে ম্যাচ করতে পারে। যেমন প্যাটার্ন $a*c$ টেক্সট $abccaacc$-এ ঠিক তিনটি পজিশনে আছে, ইনডেক্স $0$, ইনডেক্স $4$ এবং ইনডেক্স $5$-এ।
আমরা হুবহু একই পলিনোমিয়াল তৈরি করি, শুধু $P[m-i-1] = *$ হলে $b_i = 0$ সেট করি। $P$-তে ওয়াইল্ডকার্ডের সংখ্যা $x$ হলে, $c_{m-1+i} = m - x$ হলে $T$-তে ইনডেক্স $i$-এ $P$-এর ম্যাচ পাওয়া যাবে।
অনুশীলন সমস্যা#
- SPOJ - POLYMUL
- SPOJ - MAXMATCH
- SPOJ - ADAMATCH
- Codeforces - Yet Another String Matching Problem
- Codeforces - Lightsabers (hard)
- Codeforces - Running Competition
- Kattis - A+B Problem
- Kattis - K-Inversions
- Codeforces - Dasha and cyclic table
- CodeChef - Expected Number of Customers
- CodeChef - Power Sum
- Codeforces - Centroid Probabilities