با دریافت دو رشته text و pattern، تمام اندیسهای شروعی را که در آنها pattern درون text ظاهر میشود، با استفاده از الگوریتم Knuth-Morris-Pratt (KMP) پیدا کنید و آنها را بهترتیب صعودی برگردانید.
1. تمام تطابقهای همپوشان (Overlapping Occurrences) باید گزارش شوند:
برای مثال، رشته "aa" درون "aaa" در دو اندیس 0 و 1 ظاهر میشود. بنابراین، هر دو اندیس باید در خروجی قرار بگیرند.
2. اندیسها از صفر شروع میشوند (0-based):
یعنی اولین کاراکتر رشته دارای اندیس 0 است.
3. استفاده از روشهای آماده جستوجوی رشته ممنوع است:
استفاده از موارد زیر مجاز نیست:
str.findstr.indexinreسیستم داوری (Judge) کد منبع را برای بررسی این موارد بازرسی میکند؛ زیرا بررسی صرفاً خروجی نمیتواند تقلب را تشخیص دهد. دلیلش این است که توابع و عملگرهای داخلی زبان میتوانند دقیقاً همان خروجی مورد انتظار را تولید کنند.
4. تابع شکست الگوریتم KMP (جدول LPS) باید مستقیماً از روی رشته pattern محاسبه شود:
پیچیدگی زمانی محاسبه این جدول باید برابر با O(len(pattern)) باشد.
1 <= len(text) <= 10^61 <= len(pattern) <= len(text)"ababcababab" "abab"
[0,5,7]
"aaaa" "aa"
[0,1,2]
"abcabcabc" "abcabc"
[0,3]
برای دسترسی به محیط کدنویسی آنلاین و ارسال راهحل، ثبتنام کنید.
قبلاً ثبتنام کردهاید؟ وارد شوید