Pagini recente » Cod sursa (job #1911519) | Cod sursa (job #1121908) | Cod sursa (job #1072319) | Cod sursa (job #1437781) | Cod sursa (job #2349600)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int l=2000005;
char c[l],d[l];
int lps[l],n,m,cont,v[2005];
void lp()
{
int i=1,inc=0;
while(i<n)
{
if(c[i]==c[inc])
{
inc++;
lps[i++]=inc;
}
else
{
if(inc==0)++i;
else
inc=lps[inc-1];
}
}
}
void sol()
{
int i=0,inc=0;
while(i<m)
{
if(d[i]==c[inc])
{
++inc;
++i;
if(inc==n)
{
++cont;
if(cont<1005)
v[cont]=i-n;
inc=lps[inc-1];
}
}
else
{
if(inc==0)
{
i++;
}
else
{
inc=lps[inc-1];
}
}
}
}
int main()
{
in.getline(c,l);
in.getline(d,l);
n=strlen(c),m=strlen(d);
lp();
sol();
out<<cont<<'\n';
cont=min(1000,cont);
for(int i=1;i<=cont;i++)
{
out<<v[i]<<' ';
}
return 0;
}