الگوریتم Z
Z Algorithmالگوریتم Z یک الگوریتم از دسته رشته‌ها است. این الگوریتم رشته‌ای روی characterها، prefix/suffix یا state تطبیق/ویرایش کار می‌کند و تلاش می‌کند مقایسه‌های تکراری را کم کند.
اول این مفهوم را در ذهن نگه دار
الگوریتم Z یک الگوریتم از دسته رشته‌ها است. این الگوریتم رشته‌ای روی characterها، prefix/suffix یا state تطبیق/ویرایش کار می‌کند و تلاش می‌کند مقایسه‌های تکراری را کم کند.
چطور کار می‌کند؟ ساده و مرحله‌ای
برای فهم الگوریتم Z ابتدا invariant و stateای را پیدا کن که در هر مرحله تغییر می‌کند.
پیچیدگی معمول این موضوع Varies by implementation / input constraints است؛ آن را از روی loop، recursion، عملیات ساختمان داده و constraintهای ورودی تحلیل کن، نه فقط از حفظ.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
فرض‌های Unicode، case و normalization را روشن کن.
indexها یا prefix state را تعریف کن.
اگر الگوریتم اجازه می‌دهد اطلاعات match قبلی را reuse کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای الگوریتم Z هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
Varies by implementation / input constraints
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی جست‌وجو روی متن بزرگ یا تکراری است و روش naive گران می‌شود از الگوریتم تخصصی استفاده کن.
کجا معمولاً اشتباه می‌کنیم؟
- نادیده گرفتن Unicode.
- قاطی کردن Substring و Subsequence.
- خطای index/prefix.
مدل یک پاسخ حرفه‌ای
برای توضیح حرفه‌ای الگوریتم Z در مصاحبه، مسئله‌ای که حل می‌کند، invariant، state یا ساختمان داده اصلی، پیچیدگی Varies by implementation / input constraints و شرایطی که باعث می‌شود روش دیگری انتخاب کنی را بگو.
الگوریتم Z چه مسئله‌ای را حل می‌کند؟
الگوریتم Z یک الگوریتم از دسته رشته‌ها است. این الگوریتم رشته‌ای روی characterها، prefix/suffix یا state تطبیق/ویرایش کار می‌کند و تلاش می‌کند مقایسه‌های تکراری را کم کند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا Varies by implementation / input constraints است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
نادیده گرفتن Unicode.