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

Z-function و نحوه‌ی محاسبه‌ی آن

فرض کنید یک رشته $s$ به طول $n$ به ما داده شده است. Z-function برای این رشته، یک آرایه به طول $n$ است که در آن، عنصر $i$-ام برابر با بزرگترین تعداد کاراکترهایی است که از موقعیت $i$ شروع شده و با کاراکترهای ابتدایی رشته $s$ یکسان هستند.

به عبارت دیگر، $z[i]$ طول بلندترین رشته‌ای است که همزمان پیشوندی از $s$ و پیشوندی از پسوند $s$ که از خانه‌ی $i$ شروع می‌شود، است.

نکته. در این مقاله، برای جلوگیری از ابهام، از اندیس‌گذاری ۰-پایه استفاده می‌کنیم؛ یعنی اولین کاراکتر $s$ اندیس ۰ و آخرین کاراکتر اندیس $n-1$ را دارد.

اولین عنصر Z-function، یعنی $z[0]$، به طور کلی تعریف مشخصی ندارد. در این مقاله فرض می‌کنیم که مقدار آن صفر است (هرچند این موضوع تغییری در پیاده‌سازی الگوریتم ایجاد نمی‌کند).

این مقاله الگوریتمی برای محاسبه‌ی Z-function در زمان $O(n)$ و همچنین کاربردهای مختلف آن را ارائه می‌دهد.

مثال‌ها

برای مثال، در اینجا مقادیر Z-function برای رشته‌های مختلف محاسبه شده است:

  • "aaaaa" - $[0, 4, 3, 2, 1]$
  • "aaabaab" - $[0, 2, 1, 0, 2, 1, 0]$
  • "abacaba" - $[0, 0, 1, 0, 3, 0, 1]$

الگوریتم ساده

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

vector<int> z_function_trivial(string s) {
    int n = s.size();
    vector<int> z(n);
    for (int i = 1; i < n; i++) {
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
    }
    return z;
}

ما به سادگی در تمام موقعیت‌های $i$ پیمایش می‌کنیم و برای هر کدام $z[i]$ را به‌روز می‌کنیم، با شروع از $z[i] = 0$ و افزایش آن تا زمانی که به یک عدم تطابق برخورد کنیم (و تا زمانی که به انتهای خط نرسیم).

البته، این یک پیاده‌سازی بهینه نیست. اکنون به ساخت یک پیاده‌سازی بهینه خواهیم پرداخت.

الگوریتم بهینه برای محاسبه Z-function

برای به دست آوردن یک الگوریتم بهینه، مقادیر $z[i]$ را به ترتیب از $i = 1$ تا $n - 1$ محاسبه می‌کنیم، اما همزمان، هنگام محاسبه‌ی یک مقدار جدید، سعی می‌کنیم از مقادیر محاسبه‌شده‌ی قبلی بهترین استفاده‌ی ممکن را ببریم.

برای اختصار، زیررشته‌هایی که با پیشوندی از $s$ منطبق هستند را تطابق‌های قطعه‌ای می‌نامیم. برای مثال، مقدار Z-function مورد نظر، $z[i]$، طول تطابق قطعه‌ای است که از موقعیت $i$ شروع می‌شود (و در موقعیت $i + z[i] - 1$ پایان می‌یابد).

برای این کار، ما اندیس‌های $[l, r)$ راست‌ترین تطابق قطعه‌ای را نگه می‌داریم. یعنی، در میان تمام قطعات تطابقی که پیدا کرده‌ایم، آنی را نگه می‌داریم که در سمت راست‌ترین نقطه تمام می‌شود. در واقع، اندیس $r$ را می‌توان به عنوان «مرزی» در نظر گرفت که رشته $s$ تا آنجا توسط الگوریتم پیمایش شده است؛ هر چیزی فراتر از آن نقطه هنوز ناشناخته است.

سپس، اگر اندیس کنونی (که باید مقدار بعدی Z-function را برای آن محاسبه کنیم) برابر با $i$ باشد، یکی از دو گزینه را داریم:

  • $i \geq r$ -- موقعیت کنونی خارج از آن چیزی است که قبلاً پردازش کرده‌ایم.

    سپس $z[i]$ را با الگوریتم ساده محاسبه می‌کنیم (یعنی فقط مقایسه کاراکتر به کاراکتر). توجه داشته باشید که در پایان، اگر $z[i] > 0$ باشد، باید اندیس‌های راست‌ترین قطعه را به‌روز کنیم، زیرا تضمین می‌شود که $r$ جدید یعنی $i + z[i]$ از $r$ قبلی بهتر است.

  • $i < r$ -- موقعیت کنونی داخل تطابق قطعه‌ای فعلی $[l, r)$ است.

    سپس می‌توانیم از مقادیر Z-function محاسبه‌شده برای «مقداردهی اولیه» به $z[i]$ استفاده کنیم (که قطعاً بهتر از «شروع از صفر» است)، شاید حتی با یک عدد بزرگ.

    برای این کار، مشاهده می‌کنیم که زیررشته‌های $s[l \dots r)$ و $s[0 \dots r-l)$ تطابق دارند. این بدان معناست که به عنوان یک تقریب اولیه برای $z[i]$ می‌توانیم مقداری را که قبلاً برای قطعه متناظر $s[0 \dots r-l)$ محاسبه شده است، یعنی $z[i-l]$، در نظر بگیریم.

    با این حال، مقدار $z[i-l]$ ممکن است بیش از حد بزرگ باشد: وقتی برای موقعیت $i$ اعمال شود، ممکن است از اندیس $r$ فراتر رود. این مجاز نیست زیرا ما در مورد کاراکترهای سمت راست $r$ چیزی نمی‌دانیم: آنها ممکن است با آنچه لازم است متفاوت باشند.

    در اینجا یک مثال از سناریوی مشابه آورده شده است:

    $$ s = "aaaabaa" $$

    هنگامی که به آخرین موقعیت ($i = 6$) می‌رسیم، قطعه تطابق فعلی $[5, 7)$ خواهد بود. موقعیت $6$ با موقعیت $6 - 5 = 1$ مطابقت دارد که مقدار Z-function برای آن $z[1] = 3$ است. واضح است که نمی‌توانیم $z[6]$ را با $3$ مقداردهی اولیه کنیم؛ این کاملاً نادرست خواهد بود. حداکثر مقداری که می‌توانیم با آن مقداردهی اولیه کنیم $1$ است - زیرا این بزرگترین مقداری است که ما را از اندیس $r$ قطعه تطابق $[l, r)$ فراتر نمی‌برد.

    بنابراین، به عنوان یک تقریب اولیه برای $z[i]$ می‌توانیم با خیال راحت در نظر بگیریم:

    $$ z_0[i] = \min(r - i,\; z[i-l]) $$

    پس از مقداردهی اولیه $z[i]$ به $z_0[i]$، سعی می‌کنیم $z[i]$ را با اجرای الگوریتم ساده افزایش دهیم - زیرا به طور کلی، پس از مرز $r$، نمی‌توانیم بدانیم که آیا تطابق قطعه ادامه خواهد داشت یا نه.

بنابراین، کل الگوریتم به دو حالت تقسیم می‌شود که فقط در مقدار اولیه $z[i]$ تفاوت دارند: در حالت اول فرض می‌شود صفر است، در حالت دوم توسط مقادیر محاسبه‌شده‌ی قبلی تعیین می‌شود (با استفاده از فرمول بالا). پس از آن، هر دو شاخه این الگوریتم را می‌توان به پیاده‌سازی الگوریتم ساده کاهش داد، که بلافاصله پس از مشخص کردن مقدار اولیه شروع می‌شود.

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

پیاده‌سازی

پیاده‌سازی کاملاً مختصر است:

vector<int> z_function(string s) {
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = 0;
    for(int i = 1; i < n; i++) {
        if(i < r) {
            z[i] = min(r - i, z[i - l]);
        }
        while(i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
        if(i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

توضیحاتی در مورد این پیاده‌سازی

کل راه حل به صورت تابعی ارائه شده است که یک آرایه به طول $n$ - یعنی Z-function رشته $s$ - را برمی‌گرداند.

آرایه $z$ در ابتدا با صفر پر می‌شود. فرض می‌شود که راست‌ترین قطعه تطابق فعلی $[0; 0)$ است (یعنی یک قطعه عمداً کوچک که هیچ $i$ را شامل نمی‌شود).

داخل حلقه برای $i = 1 \dots n - 1$ ابتدا مقدار اولیه $z[i]$ را تعیین می‌کنیم - این مقدار یا صفر باقی می‌ماند یا با استفاده از فرمول بالا محاسبه می‌شود.

پس از آن، الگوریتم ساده تلاش می‌کند تا مقدار $z[i]$ را تا حد امکان افزایش دهد.

در نهایت، اگر لازم باشد (یعنی اگر $i + z[i] > r$ باشد)، راست‌ترین قطعه تطابق $[l, r)$ را به‌روز می‌کنیم.

رفتار مجانبی الگوریتم

ما ثابت خواهیم کرد که الگوریتم بالا زمان اجرای خطی نسبت به طول رشته دارد - یعنی $O(n)$ است.

اثبات بسیار ساده است.

تمرکز ما بر روی حلقه تو در توی while است، زیرا بقیه موارد فقط مجموعه‌ای از عملیات با هزینه ثابت هستند که در مجموع $O(n)$ می‌شوند.

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

برای این کار، هر دو شاخه الگوریتم را در نظر می‌گیریم:

  • $i \geq r$

    در این حالت، یا حلقه while هیچ تکراری نخواهد داشت (اگر $s[0] \ne s[i]$)، یا چند تکرار خواهد داشت که از موقعیت $i$ شروع شده و هر بار یک کاراکتر به سمت راست حرکت می‌کند. پس از آن، مرز راست $r$ لزوماً به‌روز خواهد شد.

    بنابراین متوجه شدیم که وقتی $i \geq r$ است، هر تکرار حلقه while مقدار اندیس $r$ جدید را افزایش می‌دهد.

  • $i < r$

    در این حالت، $z[i]$ را با مقدار مشخص $z_0$ که از فرمول بالا به دست آمده، مقداردهی اولیه می‌کنیم. بیایید این مقدار اولیه $z_0$ را با مقدار $r - i$ مقایسه کنیم. سه حالت خواهیم داشت:

    • $z_0 < r - i$

      ثابت می‌کنیم که در این حالت هیچ تکراری از حلقه while رخ نخواهد داد.

      اثبات آن آسان است، برای مثال با برهان خلف: اگر حلقه while حداقل یک تکرار داشته باشد، به این معنی است که تقریب اولیه $z[i] = z_0$ نادرست بوده (کمتر از طول واقعی تطابق). اما از آنجا که $s[l \dots r)$ و $s[0 \dots r-l)$ یکسان هستند، این امر به این معنی است که $z[i-l]$ مقدار اشتباهی را در خود نگه داشته است (کمتر از آنچه باید باشد).

      بنابراین، از آنجا که $z[i-l]$ صحیح و کمتر از $r - i$ است، نتیجه می‌شود که این مقدار با مقدار مورد نیاز $z[i]$ منطبق است.

    • $z_0 = r - i$

      در این حالت، حلقه while ممکن است چند تکرار داشته باشد، اما هر یک از آنها منجر به افزایش مقدار اندیس $r$ خواهد شد، زیرا ما مقایسه را از $s[r]$ شروع خواهیم کرد که از بازه $[l, r)$ فراتر خواهد رفت.

    • $z_0 > r - i$

      این گزینه، طبق تعریف $z_0$، غیرممکن است.

بنابراین، ثابت کردیم که هر تکرار حلقه داخلی باعث می‌شود که اشاره‌گر $r$ به سمت راست حرکت کند. از آنجا که $r$ نمی‌تواند بیشتر از $n-1$ باشد، این بدان معناست که حلقه داخلی بیش از $n-1$ تکرار نخواهد داشت.

از آنجا که بقیه الگوریتم به وضوح در $O(n)$ کار می‌کند، ثابت کردیم که کل الگوریتم محاسبه Z-function در زمان خطی اجرا می‌شود.

کاربردها

اکنون به بررسی برخی از کاربردهای Z-function برای وظایف خاص می‌پردازیم.

این کاربردها تا حد زیادی شبیه به کاربردهای prefix function هستند.

جستجوی زیررشته

برای جلوگیری از سردرگمی، $t$ را رشته متن و $p$ را الگو می‌نامیم. مسئله این است: تمام رخدادهای الگوی $p$ را در متن $t$ پیدا کنید.

برای حل این مسئله، رشته جدیدی به صورت $s = p + \diamond + t$ می‌سازیم، یعنی رشته‌های $p$ و $t$ را به هم می‌چسبانیم اما یک کاراکتر جداکننده $\diamond$ نیز در وسط قرار می‌دهیم (ما $\diamond$ را طوری انتخاب می‌کنیم که مطمئناً در هیچ کجای رشته‌های $p$ یا $t$ وجود نداشته باشد).

Z-function را برای $s$ محاسبه کنید. سپس برای هر $i$ در بازه $[0; \; \operatorname{length}(t) - 1]$، مقدار متناظر $k = z[i + \operatorname{length}(p) + 1]$ را در نظر می‌گیریم. اگر $k$ برابر با $\operatorname{length}(p)$ باشد، می‌دانیم که یک رخداد از $p$ در موقعیت $i$-ام از $t$ وجود دارد، در غیر این صورت هیچ رخدادی از $p$ در موقعیت $i$-ام از $t$ وجود ندارد.

زمان اجرا (و مصرف حافظه) $O(\operatorname{length}(t) + \operatorname{length}(p))$ است.

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

با داشتن یک رشته $s$ به طول $n$، تعداد زیررشته‌های متمایز $s$ را بشمارید.

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

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

رشته $t = s + c$ را برداشته و آن را معکوس کنید (کاراکترهای آن را به ترتیب معکوس بنویسید). وظیفه ما اکنون شمارش تعداد پیشوندهایی از $t$ است که در هیچ جای دیگری از $t$ یافت نمی‌شوند. Z-function رشته $t$ را محاسبه کرده و مقدار بیشینه آن $z_{max}$ را پیدا می‌کنیم. بدیهی است که پیشوند $t$ به طول $z_{max}$ در جای دیگری در وسط $t$ نیز رخ می‌دهد. واضح است که پیشوندهای کوتاه‌تر نیز رخ می‌دهند.

بنابراین، متوجه شدیم که تعداد زیررشته‌های جدیدی که هنگام اضافه شدن نماد $c$ به $s$ ظاهر می‌شوند برابر است با $\operatorname{length}(t) - z_{max}$.

در نتیجه، زمان اجرای این راه حل برای یک رشته به طول $n$ برابر با $O(n^2)$ است.

شایان ذکر است که دقیقاً به همین روش می‌توانیم، باز هم در زمان $O(n)$، تعداد زیررشته‌های متمایز را هنگام اضافه کردن یک کاراکتر به ابتدای رشته و همچنین هنگام حذف آن (از انتها یا ابتدا) دوباره محاسبه کنیم.

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

یک رشته $s$ به طول $n$ داده شده است. کوتاه‌ترین نمایش «فشرده» آن را پیدا کنید، یعنی: کوتاه‌ترین رشته $t$ را پیدا کنید به طوری که $s$ بتواند به صورت الحاق یک یا چند کپی از $t$ نمایش داده شود.

یک راه حل این است: Z-function رشته $s$ را محاسبه کنید، در تمام $i$ هایی که $i$ بر $n$ بخش‌پذیر است، حلقه بزنید. در اولین $i$ که $i + z[i] = n$ باشد، متوقف شوید. سپس، رشته $s$ می‌تواند به طول $i$ فشرده شود.

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

مسائل تمرینی