Pagini recente » Cod sursa (job #657323) | Cod sursa (job #676363) | Cod sursa (job #622960) | Cod sursa (job #997713) | Cod sursa (job #1074934)
#include <iostream>
#include <string>
#include <fstream>
#include <vector>
using namespace std;
string s1,s2;
vector<int> p;
int n,m;
void prefix()
{
int k;
k=0; // lungimea celui mai lung prefix care e si sufix
p[1]=0; //vectorul prefix
for(int i=2;i<=n;i++)
{
while(k && s1[k+1]!=s1[i]) // daca nu gasesc o potrivire dar exista o potrivire anterioara
k=p[k]; // aduc potrivirile la potrivirile ,prefixul, din subsirul de la 1 la i
// se repeta pana se gaseste potrivirea sau pana nu mai exista un subsir ,anume de la 1 la 0
if(s1[k+1]==s1[i])
k++; // in caz de potrivire creste k
p[i]=k; // marchez in p lungimea prefixului gasit
// e mereu maximul aviz pt Lacraru
}
}
int main()
{
int k=0;
vector <int> r;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
getline(in,s1);
s1="*"+s1; // uitasem ,dar sirul trebuie indentat de la 1 la n daca are lungimea n
// adaug un caracter oarecare la inceput ,nu e folosit niciodata
getline(in,s2);
s2="%"+s2;
n=s1.size()-1;
m=s2.size()-1;
p.reserve(n);
prefix();
// secventa de cod care verifica e asemanatoare cu construirea prefixuli
//doar ca fac verificarile cu caractere din ambele siruri
for(int i=1;i<=m;i++)
{
while(k && s1[k+1]!=s2[i])// daca nu se potrivesc si exista o potrivire anterioara
k=p[k]; //verific de la prefixul potriviri anterioare
if(s1[k+1]==s2[i]) // am gasit o potrivire
k++; // cresc numarul de caractere care au fost potrivite pana acum
if(k==n)// am gasit o aparitie a lui s1 in s2
{
// aici depinde de problema si ce vrei sa faci cu aparitia
r.push_back(i-n);
k=p[k];
}
}
cout<<r.size()<<"\n";
for(int i=0;i<r.size();i++)
cout<<r[i]<<" ";
return 0;
}