Призначення

У школі-інтернаті Янко ділить холодильник з ще трьома людьми. Часто трапляється так, що їжа, яку він в неї вкладає, загадково зникає звідти. Наприклад, минулої неділі він приніс із дому смачну курячу ніжку на грилі з рисом і сирним соусом. Він поклав його на полицю холодильника, з’ївши у ніч на понеділок.

нерегулярної

У ніч на понеділок о 19 годині він цілими днями повертався до гуртожитку на факультеті, голодний, як вовк. Він відкрив холодильник і що він тут бачить? Нічого! Стегно та його ідеї про смачну вечерю зникли.

Він сказав собі, що так не може тривати далі, і він придумав: він буде зберігати в холодильнику не їстівні речі, крім їстівних. Він загортає все у фольгу, щоб його співмешканці не знали, що відбувається.

Проблема в тому, що він не буде знати, що їсти безпечно. На щастя, Янко нещодавно дізнався про шифри в школі, тому знає, як маркувати упаковки, щоб лише він знав їх вміст.

Тож він створив таблицю, в якій присвоїв кожній малій літери англійського алфавіту рівно одну велику букву англійського алфавіту. Він позначив пакунки двома словами. Перша складається з малих літер англійського алфавіту, а друга з великих літер англійського алфавіту. Якщо в упаковці є їжа, тоді друге слово утворюється від першого відповідно до цієї таблиці.

Сусідні кімнати Янека, які не знають цього коду, цілком можуть скористатися неїстівними упаковками, які можуть містити, наприклад, дерево або капсули з пральним порошком.

Напишіть Янеку програму, яка допоможе йому з’ясувати, чи є упаковка їстівною.

Завдання

Біля входу знаходиться список пакунків у холодильнику. На кожному з них є рівно два слова. Відповідно до слів на кожній упаковці з’ясуйте, чи є в ній їжа. У упаковці є їжа саме тоді, коли:

  • Кожній букві в першому слові присвоюється рівно одна велика буква (зображення) у другому слові.
  • Ті самі літери мають однакове зображення.
  • Різні букви мають різне зображення.
  • Порядок зображень у другому слові відповідає порядку букв у першому слові.

Формат введення

Перший рядок введення містить число \ (1 \ leq t \ leq 10 ^ 4 \), кількість упаковок у холодильнику. Далі наводяться описи \ (t \) пакетів - два рядки, що містять слова на кожному пакунку. Перше слово складається з малих літер, а друге - з великих літер англійського алфавіту. Кожне слово містить принаймні один символ. Сума довжин усіх слів не перевищує \ (4 \, 000 \, 000 \) .

Вихідний формат

Напишіть "так" для кожного вихідного пакета, якщо в ньому є їжа, інакше напишіть "ні".

Приклади

Вхідні дані:

Вихід:

Від слова "anna" "a" з'явилося робити "A" і "n" до "B"

Слово "ABB" коротше, ніж "anna", тому неправда, що кожна буква першого слова є просто Жита відображається до другого.

У слові «куля» жодна буква не повторюється, тому п’ять букв відображаються на п’яти різних зображеннях.

Слово `` банани '' неправильно відображалося у слові `` АНАНАС '', оскільки до двох літер `` b '' та `` n '' присвоєно `` A ''.

Завдання говорить, що у нас є два рядки на вході, і наше завдання - з’ясувати, чи відповідають вони зазначеним умовам. Ми можемо узагальнити умови, щоб кожен однаковий (малий) символ першого слова повинен відповідати однаковим (великим) символам - зображенням - у другому слові. Різні символи першого слова повинні мати різні зображення у другому.

Функціональне рішення

У найпростішому рішенні досить пройти всі пари символів вихідного слова та перевірити, чи виконуються умови з вводу.

Перш за все перевіряємо, чи однакові слова однакової довжини. Якщо вони не є, ми знаємо, що деякий символ першого слова не має зображення у другому слові, або навпаки, і тому ми можемо відразу сказати, що відповідь "ні".

Тепер йде основна частина рішення. Скажімо, ми маємо обидва рядки \ (A \) та \ (B \) довжини \ (n \) прочитані в пам'яті та перебираємо обидва слова символ за символом. Мета - перевірити, чи всі символи відповідають заданим умовам введення. Для кожної \ (i \) -ї пари символів \ (A_i \) та \ (B_i \) ми передаємо інші \ (n - i \) пари \ (A_j \), \ (B_j \). Під час цього переходу можуть виникнути 4 ситуації:

\ (A_j \), \ (B_j \) збігаються \ (A_i \), \ (B_i \) - тоді все добре. \ (A_i = A_j \) і тому їх зображення однакові \ (B_i = B_j \) .

\ (A_i \ neq A_j \) та \ (B_i \ neq B_j \) - тоді все теж добре. Оригінальні літери різні, і тому їх зображення різні.

\ (A_i = A_j \) та \ (B_i \ neq B_j \) (або навпаки \ (A_i \ neq A_j \) та \ (B_i = B_j \)) означає, що в оригінальному слові ми маємо дві однакові літери що вони мають різні зображення, або, в останньому випадку, це різні букви в оригінальному слові і мають однакові зображення. Обидва ці випадки означають, що ми знайшли персонажа, який не відповідає умові завдання, і тому відповідь "ні".

Якщо ми переглядаємо ціле слово таким чином і не знаходимо жодної помилки, умови виконуються для всіх символів, і тому відповідь "так".

Складність у часі цього рішення \ (O (n ^ 2) \), тоді як для кожної з позицій \ (n \) \ (i \) нам все одно потрібно пройти порядок \ (n \) позицій \ (j \) .

Складність пам'яті є \ (O (n) \), тому що ми пам’ятаємо два слова з \ (n \) літерами.

На вході, однак, ми можемо отримати слово довжиною до \ (2 \, 000 \, 000 \), що означає, що із зазначеною вище складністю часу рішення буде працювати відносно довго ...

Шифр заміщення

Однак ми можемо спростити та переформулювати умови з присвоєння, щоб ми хотіли, щоб кожна буква нижнього регістру (від першого слова) була зашифрована до літери верхнього регістру (від другого слова). Також має бути правдою, що до однієї і тієї ж великої літери не можна зашифрувати дві маленькі літери.

Зверніть увагу, що таке шифрування можна повністю визначити за допомогою алфавіт шифрування, це рядок, у якому зашифрований символ (зображення) \ (i \) цієї літери класичного алфавіту знаходиться на \ (i \) -му місці. Наприклад, використання алфавіту шифрування ANCDEFGHIJKLMBOPQRSTUVWXYZ робить слово «abba» словом «ANNA». Буква a змінюється на A, b на N .

Таке шифрування зазвичай називають замінний шифр. Наше завдання - з’ясувати, чи зашифрований текст міг походити з оригіналу за допомогою такого шифру.

Краще рішення

І саме за допомогою алфавіту шифрування ми можемо розробити швидше рішення! Якщо ми пам’ятаємо алфавіт шифрування, то нам не потрібно переглядати решту слова для кожного символу, а нам потрібно лише перевірити, чи всі нові символи зашифровані відповідно до того ж алфавіту, що і попередні символи.

Ми запам’ятаємо два алфавіти шифрування, завдяки яким ми зможемо реалізувати шифрування та дешифрування. Один алфавіт зашифрує символи вихідного слова в шифр, а інший буде зворотним до нього - якщо алфавіт шифрування змінює a на B, тоді алфавіт дешифрування змінює B на a .

Для кожного символу \ (i \) -ти з вихідного слова ми з’ясуємо, чи вже в алфавіті є зображення, призначене йому для шифрування. Якщо зображення немає, це означає, що ми вперше виявили такий лист. У цьому випадку ми призначаємо зображення символу відповідно до його шифру, тобто символу \ (i \) у другому слові.

Ми знаходимо те саме для символів у другому, зашифрованому слові, і створюємо алфавіт для розшифровки.

Якщо \ (i \) -й символ уже має зображення, пов'язане з ним в алфавіті шифрування, ми перевіряємо, що це зображення відповідає \ (i \) -му символу у другому слові. Якщо вони не збігаються, ми виявили помилку шифрування - два однакові символи зашифровані на різних зображеннях. Нам також потрібно перевірити, що інший символ випадково не зашифрований на зображенні \ (i \) -th. Ми перевіримо це, використовуючи розроблений на сьогодні алфавіт.

Складність пам'яті в основному така ж, як і раніше, хоча зараз ми маємо запам'ятати два алфавіти - \ (2 \ раз 26 \) символів. Це означає \ (O (2 \ разів n + 2 \ разів 26) \), але ми можемо нехтувати константами при оцінці складності, оскільки нас цікавить лише порядок оцінки обсягу використаної пам'яті. Таким чином, ми можемо визначити складність пам'яті, що виникає в результаті \ (O (n) \) .

З плином часу ми отримуємо значне вдосконалення і доходимо до лінійної складності, оскільки виконуємо лише постійну кількість операцій для кожної букви. Тому. \ (O (n) \) .

Обговорення

Тут ви можете вільно обговорювати рішення, ділитися своїми фрагментами коду тощо.

Ви повинні увійти, щоб додати коментарі.