Pagini recente » Cod sursa (job #1957215) | Cod sursa (job #2082602) | Cod sursa (job #1561713) | Cod sursa (job #1873745) | Cod sursa (job #2139646)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define maxn 2000002
using namespace std;
string S, P, str;
int Z[2*maxn];
vector<int> aparitii;
void build_Z_array()
{
int L, R;
L = R = 0;
for (int i = 1; i < str.size(); ++i)
{
if(i > R)
{
L = R = i;
while(R < str.size() && str[R - L] == str[R])
++R;
Z[i] = R - L;
--R;
}
else
{
int k = i - L;
if(Z[k] < R - i +1)
Z[i] = Z[k];
else
{
while(R < str.size() && str[R - L] == str[R])
++R;
Z[i] = R - L;
--R;
}
}
}
}
int main()
{
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
//necesar pt a testa codul cu problema de pe infoarena
in>>P>>S;
str = P;
str+='$';
str+=S;
build_Z_array();
for(int i = P.size() + 1; i < str.size(); ++i)
if(Z[i] == P.size())
{
//cout<<"Potrivire la: "<<i - P.size() - 1<<"\n";
aparitii.push_back(i - P.size() - 1);
}
int maxim = ((aparitii.size() > 1000) ? 1000 : aparitii.size());
out<<aparitii.size()<<"\n";
for(int i = 0; i < maxim; ++i)
out<<aparitii[i]<<" ";
}