| Fişierul intrare/ieşire: | diez.in, diez.out | Sursă | Urmasii lui Moisil 2016, Clasele 11-12 |
| Autor | Stefan Negrus | Adăugată de |  Paul Diac •diac_paul |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Diez
Negrimon a găsit într-o culegere această problemă #legendară: peste un şir de caractere de lungime N, alcătuit din litere mici ale alfabetului englez, se efectuează M operaţii de următoarele tipuri:
1. Se inserează în şir caracterul x, pe poziţia p, după deplasarea cu o poziţie la dreapta a caracterelor situate pe poziţiile mai mari sau egale cu p. Dacă valoarea p este egală cu lungimea şirului, x este alipit la finalul şirului.
2. Se răspunde cu 1 dacă secvenţa de litere care începe la poziţia q1 şi are lungimea lg coincide literă cu literă, cu secvenţa care începe la poziţia q2 şi are aceeaşi lungime lg şi se răspunde cu 0 în caz contrar. Este posibil ca cele două secvenţe să se suprapună complet sau parţial în şirul din care ele fac parte.
Fiind dat un şir de N litere mici şi o listă de M operaţii, să se afişeze răspunsurile la operaţiile de tip 2, respectând ordinea din succesiunea de operaţii date.
Date de intrare
Fişierul de intrare diez.in conţine pe prima linie valorile N şi M, separate printr-un spaţiu cu semnificaţia din enunţ. Pe a doua linie se află un şir de N litere mici ale alfabetului englez iar următoarele M linii conţin câte o operaţie în unul dintre formatele:
1 p x - Datele pentru operaţia de tipul 1.
2 q1 q2 lg - Datele pentru operaţia de tipul 2.
Date de ieşire
În fişierul de ieşire diez.out se vor scrie valori egale cu 0 sau 1, câte una pe o linie, reprezentând răspunsurile date, în ordine, la operaţiile de tipul 2 existente în fişierul de intrare.
Restricţii
- 1 ≤ N, M ≤ 250 000
- 0 ≤ p ≤ lungimea şirului la momentul inserării
- x este literă mică a alfabetului englez
- q1, q2 ≥ 0; se garantează că pentru fiecare operaţie de tipul 2 există lg caractere în şir începând atât cu poziţia q1 cât şi cu poziţia q2
- 1 < lg ≤ lungimea şirului la momentul efectuării operaţiei de tipul 2
- Numerotarea caracterelor din şir începe de la poziţia 0
Exemplu
| diez.in | diez.out | Explicaţii |
|---|---|---|
| 8 6 abcasfas 2 0 5 3 1 3 d 2 4 7 2 1 1 s 1 10 b 2 0 8 3 | 0 1 1 | Se compară secvenţele abc şi fas care sunt diferite → se afişează 0 Caracterul d este inserat înainte de poziţia 3 şi se obţine şirul abcdasfas Se compară subşirurile as şi as , sunt identice → se afişează 1 Caracterul s este inserat înainte de poziţia 1, se obţine şirul asbcdasfas Caracterul b este inserat pe poziţia 10, poziţia este egală cu lungimea şirului, se obţine şirul asbcdasfasb Se compară subşirurile asb si asb , sunt identice → se afişează 1 |
| 6 3 atmatm 2 0 2 4 1 6 a 2 0 3 4 | 0 1 | Se compară subşirurile atma şi matm , sunt diferite → se afişează 0 Caracterul a se alipeşte la final, se obţine şirul atmatma Se compară subşirurile atma atma , sunt identice → se afişează 1 |
