KMP Substring Search

متوسط
توضیحات

مسئله

با دریافت دو رشته text و pattern، تمام اندیس‌های شروعی را که در آن‌ها pattern درون text ظاهر می‌شود، با استفاده از الگوریتم Knuth-Morris-Pratt (KMP) پیدا کنید و آن‌ها را به‌ترتیب صعودی برگردانید.

قوانینی که باید در صورت مسئله ذکر شوند

1. تمام تطابق‌های هم‌پوشان (Overlapping Occurrences) باید گزارش شوند:

برای مثال، رشته "aa" درون "aaa" در دو اندیس 0 و 1 ظاهر می‌شود. بنابراین، هر دو اندیس باید در خروجی قرار بگیرند.

2. اندیس‌ها از صفر شروع می‌شوند (0-based):

یعنی اولین کاراکتر رشته دارای اندیس 0 است.

3. استفاده از روش‌های آماده جست‌وجوی رشته ممنوع است:

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

  • str.find
  • str.index
  • عملگر in
  • ماژول re

سیستم داوری (Judge) کد منبع را برای بررسی این موارد بازرسی می‌کند؛ زیرا بررسی صرفاً خروجی نمی‌تواند تقلب را تشخیص دهد. دلیلش این است که توابع و عملگرهای داخلی زبان می‌توانند دقیقاً همان خروجی مورد انتظار را تولید کنند.

4. تابع شکست الگوریتم KMP (جدول LPS) باید مستقیماً از روی رشته pattern محاسبه شود:

پیچیدگی زمانی محاسبه این جدول باید برابر با O(len(pattern)) باشد.

محدودیت‌ها (Constraints)

  • 1 <= len(text) <= 10^6
  • 1 <= len(pattern) <= len(text)
  • فقط حروف کوچک انگلیسی مجاز هستند.
نمونه تست‌کیس‌ها
ورودی (Input)
"ababcababab"
"abab"
خروجی (Output)
[0,5,7]
ورودی (Input)
"aaaa"
"aa"
خروجی (Output)
[0,1,2]
ورودی (Input)
"abcabcabc"
"abcabc"
خروجی (Output)
[0,3]

شروع چالش

برای دسترسی به محیط کدنویسی آنلاین و ارسال راه‌حل، ثبت‌نام کنید.

ثبت‌نام و شروع

قبلاً ثبت‌نام کرده‌اید؟ وارد شوید

آمار و محدودیت‌ها

۲۰ XP
پاداش
۲s
زمان مجاز
۲۵۰ MB
حافظه مجاز
۱
شروع
۱
حل شده

زبان‌های مجاز

python