Question

Ma poate ajuta cineva cu o problema pe pb-info. Este problema 519:

Cerința:
Se dă un vector x cu n elemente, numere naturale și un vector y cu m elemente, numere naturale. Să se verifice dacă vectorul y este secvență în vectorul x.

Date de intrare:
Programul citește de la tastatură numărul n, iar apoi n numere naturale, elementele vectorului x, apoi numărul m, iar apoi m numere naturale, elementele vectorului y.

Date de ieșire:
Programul va afișa pe ecran numărul p, reprezentând poziția din vectorul x de unde începe secvența y, dacă y este secvență în x, respectiv mesajul NU dacă y nu este secvență în x.

Restricții și precizări:
1 ≤ m ≤ n ≤ 1000
elementele celor doi vectori vor fi indexate de la 1
dacă vectorul y este de mai multe ori secvență în x se va afișa poziția de început a primei apariții.

Answer 1

Răspuns:

#include<iostream>

using namespace std;

int main(){

   long n,m,i,j;

   int x[1010],y[1010]; //Mai mult decat 1000 ca sa fii sigur

   cout<<"n="; cin>>n; //Citire n

   for(i=1;i<=n;i++) cin>>x[i]; //Citire n elemente

   cout<<"m="; cin>>m; //Citire m

   for(i=1;i<=m;i++) cin>>y[i]; //Citire m elemente

   bool secventa=0; //Presupunem ca nu e secventa pentru a putea intra in for

   for(i=1;i<=n-m+1&&!secventa;i++){ // !secventa inseamna ca secventa=1, cand gasim secventa nu mai trebuie sa cautam pentru ca se cere doar prima aparitie

       secventa=1; //Presupun ca este secventa din pozitia i a vectorului x

       for(j=1;j<=m;j++) //Parcurgem y

           if(x[i+j-1]!=y[j]) secventa=0; //Parcurgem urmatoarele j-1 pozitii pentru a verifica daca y este secventa din pozitia i, daca nu sunt egale inseamna ca nu este secventa (j-1, -1 deoarece nu incepem de pe pozitia 0 ci 1 in y)

       if(secventa) cout<<"Pozitia de inceput este: "<<i; //Daca este secventa afisam pozitia

   }

   if(!secventa) cout<<"NU"; //Daca nu este secventa NU

}

Explicație:

Explicatiie se gasesc in comentari