Pagini recente » Cod sursa (job #3336373) | Cod sursa (job #3340999) | Cod sursa (job #3311108) | Cod sursa (job #1940062) | Cod sursa (job #3334881)
#include <bits/stdc++.h>
#define LMAX 2000000
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int z[LMAX+1]; ///z[i] = lungimea maxima a prefixului sirului s care este si prefix al sufixului care incepe pe pozitia i
void z_algorithm(string& s) ///algoritmul z
{
z[0]=s.size();
int l=0, r=0; ///capetele l si r ale z-box-ului
for(int i=1; i<(int)s.size(); i++)
{
if(i>r) ///daca i este mai mare ca r, comparam fiecare caracter in mod brut
{
l=i;
r=i;
while(r<(int)s.size() && s[r-l]==s[r]) r++; ///cat timp caracterele sunt identice
r--;
z[i]=r-l+1;
}
else
{
///daca suntem in interiorul z-box-ului
int j=i-l; ///pozitia din prefix asociata lui i
if(j+z[j]<r-l+1)
{
z[i]=z[j];
}
else ///extindem z-box-ul
{
l=i;
while(r<(int)s.size() && s[r-l]==s[r]) r++; ///cat timp caracterele sunt identice
r--;
z[i]=r-l+1;
}
}
}
}
int main()
{
string a, b;
in >> a >> b;
string s=a+'$'+b;
z_algorithm(s);
int nr_potriviri=0;
vector<int> indici;
for(int i=a.size()+1; i<(int)s.size(); i++)
{
if(z[i]==(int)a.size())
{
nr_potriviri++;
if(nr_potriviri<=1000) indici.push_back(i-a.size()-1);
}
}
out << nr_potriviri << "\n";
for(auto& i : indici) out << i << " ";
return 0;
}