== include(page="template/taskheader" task_id="diez") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $diez.in$ ...
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*}.
h2. Date de ieşire
În fişierul de ieşire $diez.out$ ...
Î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.
h2. 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
h2. Exemplu
table(example). |_. diez.in |_. diez.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. 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
|
== include(page="template/taskfooter" task_id="diez") ==
