پاسخ سوال رشته‌های وارواژه کوئرا

پاسخ سوال رشته‌های وارواژه کوئرا

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

پاسخ سوال رشته‌های وارواژه کوئرا

در کمال ناباوری محمد این جمله معروفش را هم گفت و به همه ثابت کرد روش عجیبی که برای نزدیک‌ کردن فاصله ذهن‌شان پیش گرفتند جواب داد! اکنون فاصله بین ذهن محمد و عرفان به سمت صفر میل می‌کند و آن‌ها مقدار زیادی خوشحال‌اند! قبل از اینکه بالاخره شروع به توسعه دادن پروژه کنند تصمیم گرفتند که اندکی برای دست‌گرمی با هم کد بزنند ولی متاسفانه هنوز به کدزدن با زبان ++C تسلط کافی ندارند. از آن‌جایی که محمد و عرفان هیچ کدام از کارهایشان عادی نبوده، یادگیری ++Cشان هم از این قاعده مستثنی نیست! آن‌ها از شما درخواست کردند که با حل یک سوال کمک کنید تا به طور کامل به ++C مسلط شوند! رشته $S$ برای رشته $T$ یک وارواژه است اگر بتوان با جابه‌جا کردن حروف رشته S به رشته $T$ رسید. برای مثال aba وارواژه رشته aab است اما وارواژه رشته aaa نیست. رشته $S$ رشته‌ای است که شامل حروف کوچک زبان انگلیسی و تعدادی کاراکتر $?$ است. همچنان رشته $P$ رشته‌ای است که تنها شامل حروف کوچک انگلیسی است. زیررشته‌ای از S را زیررشته خوب می‌گوییم اگر بتوان با قرار دادن حروف دل‌خواه بجای ?، به وارواژه‌ای از P دست یافت.

ورودی سوال رشته‌های وارواژه

در این سوال به شما ابتدا رشته S و بعد p داده می‌شود.

$$1\le |S|,|p|\le 1000$$

خروجی سوال رشته‌های وارواژه

خروجی تنها شامل یک خط است که در آن یک عدد صحیح برابر تعداد زیر رشته‌های خوب رشته S چاپ شود.

حل سوال رشته‌های وارواژه

#include <bits/stdc++.h>
using namespace std;

int good[26] = {0};
int dp[1001][26] = {0};
int k;
bool check(int r)
{
    for(int i=0; i<26; i++)
    {
        if(r == k-1)
        {
            if(dp[r][i] > good[i])
                return false;
        }
        else if(dp[r][i]-dp[r-k][i] > good[i])
            return false;
    }
    return true;
}

int main()
{
    string s, p;
    cin >> s >> p;
    k = p.length();
    
    for(char c : p)
        good[c-'a']++;
    dp[0][(int)(s[0]-'a')]++;
    for(int i=1; i<s.length(); i++)
    {
        for(int j=0; j<26; j++)
            dp[i][j] = dp[i-1][j];
        if(s[i] != '?')
            dp[i][(int)(s[i]-'a')]++;
    }
    int cou = 0;
    for(int i=p.length()-1; i<s.length(); i++)
    {
        if(check(i))
            cou ++;
    }
    
    cout << cou << endl;
    return 0;
}

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

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