Pagini recente » Cod sursa (job #1159910) | Cod sursa (job #704929) | Cod sursa (job #1704039) | Cod sursa (job #2331819) | Cod sursa (job #3349964)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int Z[400005];
void buildZ(string& a)
{
Z[0]=0;
int best=0;//cel mai bun Z de pana acum
for(int i=1;i<a.length();i++)
{
if(i<=best+Z[best]-1)//daca i-ul se afla in interiorul celui mai bun Z de pana acum
Z[i]=min(best+Z[best]-i,Z[i-best]);
while(a[i+Z[i]]==a[Z[i]])
Z[i]++;
if(best+Z[best]<i+Z[i])
best=i;
}
}
string a,b;
int main()
{
fin>>a>>b;
int cnt=0;
vector<int> pos;
int sizee=a.size();
a+='$';
a+=b;
buildZ(a);
for(int i=0;i<a.size();i++)
{
if(Z[i]==sizee)
{
cnt++;
if(pos.size()==1000)
continue;
pos.push_back(i-sizee-1);
}
}
fout<<cnt<<"\n";
for(auto it:pos)
fout<<it<<" ";
return 0;
}