Pagini recente » Cod sursa (job #169947) | dot-com/2012/clasament/runda-1 | Cod sursa (job #176154) | Clasament preONI 2007, Runda 3, Clasa a 9-a si gimnaziu | Cod sursa (job #3292641)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a, b, sir;
int z[4000002];
int main()
{
vector<int> rez;
cin>>a>>b;
sir = a;
sir += "$";
sir += b;
int n = sir.size(), best = 0, nrsecv = 0;
int la = a.size();
z[0] = 0;
for(int i = 1; i < n; ++i)
{
int capatdr = best + z[best];
int j = i - best;
if(i < capatdr)
z[i] = min(z[j], capatdr - i);
while(i + z[i] < n && sir[z[i]] == sir[i + z[i]])
{
z[i]++;
}
if(i + z[i] > capatdr)
best = i;
if(z[i] == la)
{
++nrsecv;
if(nrsecv <= 1000)
{
rez.push_back(i);
}
}
}
cout<<nrsecv<<"\n";
for(auto i : rez)
{
cout<<i - la - 1<<" ";
}
return 0;
}