Pagini recente » Cod sursa (job #2803353) | Cod sursa (job #3294498) | Cod sursa (job #2574277) | Cod sursa (job #2457320) | Cod sursa (job #3300006)
#include <bits/stdc++.h>
#define NMAX (int)2e6
#define NR_POZ 1000
using namespace std;
int pi[NMAX]; ///pi[i] = lungimea celui mai lung prefix care este si sufix sirului a[0], a[1], ... a[i]
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a, b;
cin >> a >> b;
int n=a.size(), m=b.size();
int lung_pref=0; ///lungimea unui prefix
pi[0]=lung_pref;
for(int i=1; i<n; i++)
{
while(lung_pref>0 && a[lung_pref]!=a[i]) ///cat timp nu am gasit o potrivire
{
lung_pref=pi[lung_pref-1];
}
if(a[i]==a[lung_pref]) ///daca am gasit o potrivire, marim lungimea prefixului maxim, altfel, lungimea prefixului maxim va fi 0
{
lung_pref++;
}
pi[i]=lung_pref;
}
int nr_aparitii=0; ///numarul de aparitii ale sirului a in sirul b
vector<int> poz; ///pozitiile pe care apare sirul a in sirul b
lung_pref=0; ///resetam lungimea prefixului
for(int i=0; i<m; i++)
{
while(lung_pref>0 && a[lung_pref]!=b[i]) ///cat timp nu am gasit o potrivire
{
lung_pref=pi[lung_pref-1];
}
if(b[i]==a[lung_pref]) ///daca am gasit o potrivire
{
lung_pref++;
}
if(lung_pref==n) ///daca lungimea prefixului este egala cu m, inseamna ca am gasit o aparitie a lui a in b
{
nr_aparitii++; ///marim numarul de aparitii
if(nr_aparitii<NR_POZ)
{
poz.push_back(i-n+1); ///salvam pozitia aparitiei
}
}
}
cout << nr_aparitii << "\n"; ///afisam numarul de aparitii
for(auto pozitie : poz)
cout << pozitie << " "; ///afisam pozitiile primelor 1000 de aparitii
return 0;
}