پاسخ سوال تطابق رشته کوئرا

پاسخ سوال تطابق رشته کوئرا

در این نوشته تمرین “تطابق رشته” که در وب‌سایت کوئرا موجود است را برای شما کاربران عزیز حل کرده‌ایم.

پاسخ سوال تطابق رشته کوئرا

گر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کنید، درمی‌یابید که همه استفا عاشق مصطفی هستند. در کدکاپ ۳ به هر کس ژتونی برای نهار داده شده که روی آن، رشته‌ای از حروف کوچک انگلیسی نوشته شده‌ است. محمود که یکی از استف‌های زحمت‌کش مسابقات است عقیده دارد از بین همه استف‌های عاشق مصطفی، مصطفی خودش عاشق استفی است که رشته نوشته شده روی ژتونش بیش‌ترین درجه تطابق و طول تطابق با رشته خودش را دارد. از این رو او می‌خواهد درجه تطابق و طول تطابق رشته‌ خودش را با رشته مصطفی حساب کند. درجه تطابق و طول تطابق دو رشته به شکل زیر به دست می‌آید:

رشته مصطفی را با $s$ و رشته محمود را با $t$ نشان می‌دهیم، طول هر دوی این رشته‌ها برابر $n$ است. فرض کنید یک گراف دو بخشی با $2n$ رأس داریم که رأس‌های بخش اول متناظر با کاراکترهای رشته‌ی $s$ و رأس‌های بخش دوم متناظر با کاراکترهای رشته‌ی $t$ است. به ازای هر دو اندیس $i$ و $j$ ($1\le i,j\le n$) که کاراکتر i-ام از رشته‌ی $s$ و کاراکتر j-ام از رشته‌ی t با یک‌دیگر برابر شود یک یال بین رأس‌های متناظر این دو کاراکتر در گراف می‌گذاریم. طول تطابق رشته‌های s و $t$ را برابر تعداد یال‌های بزرگ‌ترین تطابق در این گراف، و درجه تطابق رشته‌های s و t را برابر تعداد بزرگ‌ترین تطابق‌های این گراف می‌نامیم. یک تطابق در گراف یک زیرمجموعه از یال‌های آن گراف است که هیچ دو یالی از آن در رأسی مشترک نیستند. دو تطابق را متفاوت فرض می‌کنیم اگر مجموعه‌ی یال‌های آن‌ها متفاوت شود. حال محمود با دادن رشته مصطفی و رشته خودش به شما، از شما می‌خواهد که طول تطابق و باقی‌مانده درجه تطابق رشته خودش با رشته مصطفی به 9^10 + 7 را برای او بدست آورید.

ورودی سوال تطابق رشته

در خط اول $s$، که رشته مصطفی است، و در خط دوم رشته t، که رشته محمود است، به شما داده می‌شود. دقت کنید که هر دو رشته‌ فقط از حروف کوچک انگلیسی تشکیل شده است.

$$1\le |s|,|t|\le 200000$$

خروجی سوال تطابق رشته

در یک خط دو عدد جدا شده با فاصله از هم چاپ کنید که عدد اول طول تطابق دو رشته و عدد دوم باقی‌مانده درجه تطابق دو رشته به 9^10 + 7 است.

حل سوال تطابق رشته

using namespace std;
#define ll long long
const int mod = 1e9+7;
int main()
{
    string s, t;
    cin >> s >> t;
    int mini, maxi;
    ll len = 0, cnt = 1;
    for(char a='a'; a<='z'; a++)
    {
        mini = min(count(s.begin(), s.end(), a), count(t.begin(), t.end(), a));
        maxi = max(count(s.begin(), s.end(), a), count(t.begin(), t.end(), a));
        if(mini == 0) continue;
        len += mini;
        for(int i=maxi; i>maxi-mini; i--)
            cnt = (cnt*i) % mod;
    }
    
    cout << len << " " << cnt << endl;
    return 0;
}

منبع سوال‌: وب‌سایت کوئرا

اگر روش حل بهتری برای “تمرین تطابق رشته” دارید برای ما ارسال کنید تا با نام خودتان به اشتراک بگذاریم.

اگر سوال خاصی را مدنظر دارید در بخش نظرات برای ما ارسال کنید تا حل آن سوال را در الویت محتوای سایت بگذاریم.