المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۴:سوال ۱۶

الگوها

در عمل برای مشخص کردن گونه‌ای از رشته‌ها از الگوهای عام استفاده می‌کنیم. مثلا برای نشان دادن رشته‌هایی که با $h$ شروع می‌شوند و به $bak$ ختم می‌شوند، می‌توان از $h*bak$ بهره برد. یک الگوی عام رشته‌ای است که می‌تواند شامل * باشد. یک رشته $W$ با الگوی $P$ تطبیق می‌یابد اگر و تنها اگر بتوان از $P$ با جایگزین هر رشته‌ای به جای ستاره‌ها $W$ را ساخت؛ می‌توان رشته‌های مختلفی را به جای حضورهای مختلف ستاره به کار برد. $Q$ یک الگوی مشترک برای $P_1$ و $P_2$ است اگر هر رشته‌ای که با $Q$ تطبیق شود، با $P_1$ و $P_2$ هم تطبیق بشود. مجموعه‌ی $\{Q_1,Q_2,...,Q_L\}$ از الگوهای مشترک کامل است اگر هر رشته‌ای که با $P_1$ و $P_2$ تطبیق یابد، با دست کم یکی از این الگوها نیز تطبیق شود.

برنامه‌ای بنویسید که با دریافت الگوهای $P_1$ و $P_2$ برخی از اعمال زیر را انجام دهد:

  1. دست‌کم یک الگوی مشترک تولید کند؛ ولی هیچ الگوی نادرستی تولید نکند.
  2. یک مجموعه‌ی کامل از الگوهای مشترک با حداکثر ۶۶۶۶ عضو تولید کند.
  3. یک مجموعه‌ی کامل از الگوهای مشترک با کم‌ترین تعداد اعضا تولید کند.

ورودی

در هر کدام از دو سطرابتدایی فایل ورودی یکی از الگوهای $P_1$ و $P_2$ داده شده. هر کدام از این الگوها شامل حروف کوچک الفبای انگلیسی و ستاره است. طول الگوها حداکثر ۲۰ و تعداد ستاره‌ها در یک الگو حداکثر ۶ است.

خروجی

در سطر اول تعداد الگوهای مشترک و در هر یک از سطرهای دیگر یک الگو را بنویسید.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه

*ab*
ba*b
4
ba*ab*b
bab*b
ba*ab
bab

ابزار صفحه