Fişierul intrare/ieşire:diez.in, diez.outSursăUrmasii lui Moisil 2016, Clasele 11-12
AutorStefan NegrusAdăugată dediac_paulPaul Diac diac_paul
Timp execuţie pe test3 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.indiez.outExplicaţ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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?