پرش به محتویات

تابع پیشوندی. الگوریتم Knuth–Morris–Pratt

تعریف تابع پیشوندی

یک رشته $s$ به طول $n$ به شما داده می‌شود. تابع پیشوندی برای این رشته به صورت یک آرایه $\pi$ به طول $n$ تعریف می‌شود، که در آن $\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)$ است که جای بهبود دارد.

الگوریتم بهینه

این الگوریتم توسط Knuth و Pratt و به طور مستقل توسط Morris در سال ۱۹۷۷ ارائه شد. این الگوریتم به عنوان تابع اصلی یک الگوریتم جستجوی زیررشته استفاده شد.

اولین بهینه‌سازی

اولین مشاهده مهم این است که مقادیر تابع پیشوندی حداکثر می‌توانند یک واحد افزایش یابند.

در واقع، در غیر این صورت، اگر $\pi[i + 1] \gt \pi[i] + 1$ باشد، می‌توانیم این پسوند که در موقعیت $i + 1$ با طول $\pi[i + 1]$ تمام می‌شود را در نظر گرفته و آخرین کاراکتر آن را حذف کنیم. در این حالت به یک پسوند در موقعیت $i$ با طول $\pi[i + 1] - 1$ می‌رسیم که از $\pi[i]$ بهتر است، یعنی به تناقض می‌رسیم.

تصویر زیر این تناقض را نشان می‌دهد. بلندترین پسوند سره در موقعیت $i$ که پیشوند نیز هست، طول ۲ دارد و در موقعیت $i+1$ طول آن ۴ است. بنابراین رشته $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]$ باید ۳ باشد.

$$\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)$ می‌رسیم.

دومین بهینه‌سازی

بیایید فراتر رویم، می‌خواهیم از مقایسه‌های رشته‌ای خلاص شویم. برای رسیدن به این هدف، باید از تمام اطلاعات محاسبه‌شده در مراحل قبلی استفاده کنیم.

بنابراین بیایید مقدار تابع پیشوندی $\pi$ را برای $i + 1$ محاسبه کنیم. اگر $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)$ عمل انجام می‌دهد.

اینجا رویه نهایی آمده است:

  • مقادیر پیشوندی $\pi[i]$ را در یک حلقه با پیمایش از $i = 1$ تا $i = n-1$ محاسبه می‌کنیم ($\pi[0]$ به سادگی با $0$ مقداردهی می‌شود).
  • برای محاسبه مقدار فعلی $\pi[i]$، متغیر $j$ را که نشان‌دهنده طول بهترین پسوند برای $i-1$ است، تنظیم می‌کنیم. در ابتدا $j = \pi[i-1]$ است.
  • با مقایسه $s[j]$ و $s[i]$، بررسی می‌کنیم که آیا پسوند با طول $j+1$ یک پیشوند نیز هست. اگر برابر باشند، $\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$ کاراکتر اول رشته و همین تعداد از مقادیر تابع پیشوندی را ذخیره کنیم.

کاربردها

جستجوی یک زیررشته در یک رشته. الگوریتم Knuth-Morris-Pratt

این کار، کاربرد کلاسیک تابع پیشوندی است.

با داشتن یک متن $t$ و یک رشته $s$، می‌خواهیم موقعیت تمام تکرارهای رشته $s$ در متن $t$ را پیدا و نمایش دهیم.

برای راحتی، طول رشته $s$ را با $n$ و طول متن $t$ را با $m$ نشان می‌دهیم.

رشته $s + \# + t$ را تولید می‌کنیم، که در آن $\#$ یک جداکننده است که نه در $s$ و نه در $t$ ظاهر نمی‌شود. بیایید تابع پیشوندی را برای این رشته محاسبه کنیم. حال به معنای مقادیر تابع پیشوندی فکر کنید، به جز $n + 1$ ورودی اول (که به رشته $s$ و جداکننده تعلق دارند). طبق تعریف، مقدار $\pi[i]$ طول بلندترین زیررشته‌ای را نشان می‌دهد که در موقعیت $i$ به پایان می‌رسد و با پیشوند منطبق است. اما در مورد ما، این چیزی نیست جز بزرگترین بلوکی که با $s$ منطبق است و در موقعیت $i$ به پایان می‌رسد. این طول به دلیل وجود جداکننده نمی‌تواند از $n$ بزرگتر باشد. اما اگر تساوی $\pi[i] = n$ برقرار شود، به این معنی است که رشته $s$ به طور کامل در این موقعیت ظاهر می‌شود، یعنی در موقعیت $i$ به پایان می‌رسد. فقط فراموش نکنید که موقعیت‌ها در رشته $s + \# + t$ ایندکس‌گذاری شده‌اند.

بنابراین اگر در موقعیتی $i$ داشته باشیم $\pi[i] = n$، آنگاه در موقعیت $i - (n + 1) - n + 1 = i - 2n$ در رشته $t$، رشته $s$ ظاهر می‌شود.

همانطور که قبلاً در توضیحات محاسبه تابع پیشوندی ذکر شد، اگر بدانیم که مقادیر پیشوندی هرگز از یک مقدار معین تجاوز نمی‌کنند، نیازی به ذخیره کل رشته و کل تابع نداریم، بلکه فقط ابتدای آن را ذخیره می‌کنیم. در مورد ما، این بدان معناست که فقط باید رشته $s + \#$ و مقادیر تابع پیشوندی آن را ذخیره کنیم. می‌توانیم کاراکترهای رشته $t$ را یک به یک خوانده و مقدار فعلی تابع پیشوندی را محاسبه کنیم.

بنابراین الگوریتم Knuth-Morris-Pratt مسئله را در زمان $O(n + m)$ و با حافظه $O(n)$ حل می‌کند.

شمارش تعداد تکرار هر پیشوند

در اینجا دو مسئله را همزمان بررسی می‌کنیم. یک رشته $s$ به طول $n$ داده شده است. در نوع اول مسئله می‌خواهیم تعداد تکرار هر پیشوند $s[0 \dots i]$ را در خود همان رشته بشماریم. در نوع دوم مسئله، رشته دیگری به نام $t$ داده شده و می‌خواهیم تعداد تکرار هر پیشوند $s[0 \dots i]$ را در $t$ بشماریم.

ابتدا مسئله اول را حل می‌کنیم. مقدار تابع پیشوندی $\pi[i]$ را در موقعیت $i$ در نظر بگیرید. طبق تعریف، این به آن معناست که پیشوند با طول $\pi[i]$ از رشته $s$ در موقعیت $i$ رخ می‌دهد و پایان می‌یابد، و هیچ پیشوند بلندتری وجود ندارد که از این تعریف پیروی کند. همزمان، پیشوندهای کوتاه‌تر نیز می‌توانند در این موقعیت پایان یابند. دیدن این نکته دشوار نیست که ما با همان سؤالی روبرو هستیم که قبلاً هنگام محاسبه خود تابع پیشوندی به آن پاسخ دادیم: با فرض یک پیشوند به طول $j$ که پسوندی است که در موقعیت $i$ تمام می‌شود، پیشوند بعدی کوچکتر از $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$ اضافه کنیم، زیرا باید خود پیشوندهای اصلی را نیز بشماریم.

حال بیایید مسئله دوم را در نظر بگیریم. ما از ترفند Knuth-Morris-Pratt استفاده می‌کنیم: رشته $s + \# + t$ را ایجاد کرده و تابع پیشوندی آن را محاسبه می‌کنیم. تنها تفاوت با مسئله اول این است که ما فقط به مقادیر پیشوندی مربوط به رشته $t$ علاقه‌مندیم، یعنی $\pi[i]$ برای $i \ge n + 1$. با این مقادیر می‌توانیم دقیقاً همان محاسبات مسئله اول را انجام دهیم.

تعداد زیررشته‌های متمایز در یک رشته

یک رشته $s$ به طول $n$ داده شده است. می‌خواهیم تعداد زیررشته‌های متمایز ظاهر شده در آن را محاسبه کنیم.

این مسئله را به صورت تکراری حل خواهیم کرد. یعنی یاد می‌گیریم که با دانستن تعداد فعلی زیررشته‌های متمایز، چگونه این تعداد را با افزودن یک کاراکتر به انتها، دوباره محاسبه کنیم.

پس فرض کنید $k$ تعداد فعلی زیررشته‌های متمایز در $s$ باشد و ما کاراکتر $c$ را به انتهای $s$ اضافه می‌کنیم. بدیهی است که برخی زیررشته‌های جدید که به $c$ ختم می‌شوند، ظاهر خواهند شد. می‌خواهیم این زیررشته‌های جدیدی را که قبلاً ظاهر نشده‌اند، بشماریم.

رشته $t = s + c$ را گرفته و آن را معکوس می‌کنیم. حالا مسئله به محاسبه این تبدیل می‌شود که چند پیشوند وجود دارد که در هیچ جای دیگری ظاهر نمی‌شوند. اگر مقدار بیشینه تابع پیشوندی $\pi_{\text{max}}$ از رشته معکوس‌شده $t$ را محاسبه کنیم، آنگاه بلندترین پیشوندی که در $s$ ظاهر می‌شود، طول $\pi_{\text{max}}$ دارد. واضح است که تمام پیشوندهای با طول کمتر نیز در آن ظاهر می‌شوند.

بنابراین، تعداد زیررشته‌های جدیدی که با افزودن کاراکتر $c$ ظاهر می‌شوند برابر با $|s| + 1 - \pi_{\text{max}}$ است.

بنابراین برای هر کاراکتر اضافه‌شده، می‌توانیم تعداد زیررشته‌های جدید را در زمان $O(n)$ محاسبه کنیم، که در مجموع پیچیدگی زمانی $O(n^2)$ را به ما می‌دهد.

شایان ذکر است که می‌توانیم تعداد زیررشته‌های متمایز را با افزودن کاراکترها به ابتدا، یا با حذف کاراکترها از ابتدا یا انتها نیز محاسبه کنیم.

فشرده‌سازی یک رشته

یک رشته $s$ به طول $n$ داده شده است. می‌خواهیم کوتاه‌ترین نمایش «فشرده» رشته را پیدا کنیم، یعنی می‌خواهیم رشته $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$ بخش‌پذیر بود)، آنگاه تمام کاراکترهای بلوک باید یکسان باشند. اما در این صورت رشته تنها از یک کاراکتر که بارها تکرار شده تشکیل شده است، از این رو می‌توانیم آن را به رشته‌ای با اندازه ۱ فشرده کنیم، که $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 + \#$ و مقادیر تابع پیشوندی برای آن را ذخیره کنیم، و می‌توانیم تابع پیشوندی را برای تمام کاراکترهای بعدی به صورت آنی (on the fly) محاسبه کنیم:

$$\underbrace{s_0 ~ s_1 ~ \dots ~ s_{n-1} ~ \#}_{\text{need to store}} ~ \underbrace{t_0 ~ t_1 ~ \dots ~ t_{m-1}}_{\text{do not need 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 \cdot 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 \cdot n)$ می‌سازیم.

چنین آتاماتایی چه زمانی مفید است؟ برای شروع، به یاد داشته باشید که ما از تابع پیشوندی برای رشته $s + \# + t$ و مقادیر آن عمدتاً برای یک هدف واحد استفاده می‌کنیم: پیدا کردن تمام تکرارهای رشته $s$ در رشته $t$.

بنابراین، واضح‌ترین مزیت این آتاماتا تسریع در محاسبه تابع پیشوندی برای رشته $s + \# + t$ است. با ساختن آتاماتا برای $s + \#$، دیگر نیازی به ذخیره رشته $s$ یا مقادیر تابع پیشوندی در آن نداریم. تمام انتقال‌ها قبلاً در جدول محاسبه شده‌اند.

اما یک کاربرد دوم و کمتر آشکار نیز وجود دارد. می‌توانیم از آتاماتا زمانی استفاده کنیم که رشته $t$ یک رشته غول‌پیکر است که با استفاده از قوانینی ساخته شده است. این می‌تواند به عنوان مثال رشته‌های Gray باشد، یا رشته‌ای که از ترکیب بازگشتی چند رشته کوتاه از ورودی تشکیل شده است.

برای کامل بودن، چنین مسئله‌ای را حل می‌کنیم: یک عدد $k \le 10^5$ و یک رشته $s$ به طول $\le 10^5$ داده شده است. باید تعداد تکرارهای $s$ را در $k$-امین رشته Gray محاسبه کنیم. به یاد بیاورید که رشته‌های Gray به صورت زیر تعریف می‌شوند:

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

در چنین مواردی، حتی ساختن رشته $t$ به دلیل طول نجومی آن غیرممکن خواهد بود. $k$-امین رشته Gray، $2^k-1$ کاراکتر طول دارد. با این حال، می‌توانیم مقدار تابع پیشوندی را در انتهای رشته به طور مؤثر محاسبه کنیم، تنها با دانستن مقدار تابع پیشوندی در ابتدا.

علاوه بر خود آتاماتا، مقادیر $G[i][j]$ را نیز محاسبه می‌کنیم - مقدار آتاماتا پس از پردازش رشته $g_i$ با شروع از حالت $j$. و علاوه بر آن، مقادیر $K[i][j]$ را محاسبه می‌کنیم - تعداد تکرارهای $s$ در $g_i$، در حین پردازش $g_i$ با شروع از حالت $j$. در واقع $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}]$$

بنابراین می‌توانیم مسئله را برای رشته‌های Gray حل کنیم، و به طور مشابه تعداد زیادی از مسائل مشابه دیگر را نیز حل کنیم. برای مثال، دقیقاً همین روش مسئله زیر را نیز حل می‌کند: به ما یک رشته $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$ در هر یک از رشته‌ها ظاهر می‌شود را پیدا کنیم.

مسئله را می‌توان به همان روش با ساختن آتاماتای تابع پیشوندی حل کرد، و سپس انتقال‌ها را برای هر الگو با استفاده از نتایج قبلی محاسبه می‌کنیم.

مسائل تمرینی