• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

الگوریتم‌هایی وجود دارند که با استفاده از آن‌ها می‌توان رشته‌ها را به عدد تبدیل کرد. (چون کار کردن با آن‌ها راحت و سریع است.)

اگر فرض کنیم رشته داده شده تنها از حروف کوچک انگلیسی تشکیل شده است. ارزش هر حرف انگلیسی را برابر تعداد حروفی در نظر بگیرید که در الفبای انگلیسی از آن‌ها کوچک‌تر است.

برای مثال اگر این ارزش‌گذاری را با $f$ نشان‌دهیم؛ مقدار $f(a) = 0$ و مقدار $f(z) = 25$ خواهد بود.

حال برای تبدیل رشته $n$ حرفی $s=s_0 s_1 \dots s_{n - 1} ,$ به عدد به صورت زیر عمل می‌کنیم. ابتدا دو عدد صحیح و مثبت و ثابت $m$ و $b$ را در نظر می‌گیریم. سپس عدد متناظر رشته $s$ که با $hash(s)$ نمایش داده می‌شود برابر است با:

$$hash(s) = f(s_0) . b^{n - 1} + f(s_1) . b^{n - 2} + \dots + f(s_{n - 2}) . b + f(s_{n - 1}) \mod m$$

اما متاسفانه این تبدیل یک به یک نیست. یعنی ممکن است دو رشته متفاوت به یک عدد تبدیل شوند و این اتفاق خوبی نیست.

محمدحسین باقری رشته‌ها را با الگوریتم بالا به عدد تبدیل می‌کند و ادعا می‌کند که همواره رشته‌های مختلف به اعداد مختلف تبدیل می‌شوند. اما به دلیل فشار روزه، اشتباه می‌کند.

برنامه‌های زیر همگی یکسان هستند و صرفا به زبان‌های مختلف ترجمه شده است.

def hash(st, b, m):
    ret = 0
    for i in range(len(st)):
        ret = (ret * b + (ord(st[i]) - ord('a'))) % m
    return ret

n = int(input())
b = int(input())
m = int(input())

s = input()
t = input()
 
if hash(s, b, m) == hash(t, b, m):
    print('YES')
else:
    print('NO')

#include <iostream>
#include <string>

using namespace std;

int hsh(string st, int b, int m)
{
    int ret = 0;
    for (int i = 0; i < (int)st.size(); i++)
        ret = (1LL * ret * b + (st[i] - 'a')) % m;
    return ret;
}

int main()
{

    int n, b, m;
    cin >> n >> b >> m;

    string s, t;
    cin >> s >> t;

    if (hsh(s, b, m) == hsh(t, b, m))
        cout << "YES\n";
    else
        cout << "NO\n";
 
    return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), b = sc.nextInt(), m = sc.nextInt();
        String s = sc.next(), t = sc.next();
        
	if (hash(s, b, m) == hash(t, b, m))
            System.out.println("YES");
        else
            System.out.println("NO");
	}
    public static int hash(String st, int b,int m) {
        long ret = 0;
        for (int i = 0; i < st.length(); i++)
            ret = ((long)ret * (long)b + ((long)st.charAt(i) - (long)'a')) % (long)m;
        return (int)ret;
    }
}

از شما می‌خواهیم با ورودی گرفتن $n$، $b$ و $m$ دو رشته متفاوت به طول $n$ به جای $s$ و $t$ که از حروف کوچک انگلیسی تشکیل شده‌اند، چاپ کنید؛ که برنامه‌‌ی بالا به اشتباه، آن‌ها را برابر درنظر بگیرد.

ورودی

در تنها سطر ورودی سه عدد صحیح $n$، $b$ و $m$ به ترتیب ظاهر می‌شوند.

$$10 \leq n \leq 100$$ $$1 \leq b \leq 100$$ $$1\leq m \leq 10^9$$

خروجی

خروجی شامل دو سطر است:

• سطر اول خروجی، رشته $s$ که شامل $n$ حرف کوچک انگلیسی است.
• سطر دوم خروجی، رشته $t$ که شامل $n$ حرف کوچک انگلیسی است.

اگر چند جواب مختلف برای این مسئله وجود دارد یک جواب درست را به دلخواه چاپ کنید.

با توجه به محدودیت‌های سوال، می‌توان ثابت کرد که همواره حداقل یک جواب برای این مسئله وجود دارد.

مثال

ورودی نمونه ۱

10 26 2

خروجی نمونه ۱

queraquera
teamsteams

ورودی نمونه ۲

10 2 13

خروجی نمونه ۲

mzmzmzmzmz
zmzmzmzmzm