Pagini recente » Cod sursa (job #621697) | Cod sursa (job #2988203) | Cod sursa (job #1964600) | Cod sursa (job #2503178) | Cod sursa (job #1091075)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string sablon, text;
int l[2000002], v[1001], n, m;
void make_prefix()
{
int i,k;
for(i=2; i<=m; ++i)
{
k=l[i-1];
while (k && sablon[k+1]!=sablon[i])
k=l[k];
if(sablon[k+1]==sablon[i]) k++;
l[i]=k;
}
}
int main()
{
fin>>sablon>>text;
sablon=' '+sablon;
text=' '+text;
m=sablon.length()-1;
n=text.length()-1;
make_prefix();
int k=0, i, nr(0);
for(i=1; i<=n; i++)
{
while(k && sablon[k+1]!=text[i]) k=l[k];
if(sablon[k+1]==text[i])++k;
if(k==m)
{
++nr;
if(nr<=1000)v[nr]=i-m;
k=l[k];
}
}
fout<<nr<<'\n';
for(i=1; i<=min(1000,nr); ++i)
fout<<v[i]<<' ';
return 0;
}