Pagini recente » Cod sursa (job #691870) | Cod sursa (job #1744547) | Cod sursa (job #114585) | Cod sursa (job #940438) | Cod sursa (job #170050)
Cod sursa(job #170050)
#include<fstream>
#include<cstring>
using namespace std;
#define Max 2000002
char s[Max],w[Max];
int ls,lw,n,h[1000],T[Max];
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void prefix()
{
int i=2,j=0;
T[0]=-1,T[1]=0;
while(i<=lw)
{
if(w[i-1]==w[j])
{
T[i]=j+1;
i++,j++;
}
else
if(j>0)
j=T[j];
else
T[i++]=0;
}
}
void KMP()
{
prefix();
int m=0,i=0;
while(m+i<ls)
{
if(w[i]==s[m+i])
{
i++;
if(i==lw)
{
if(n<1000)
h[n]=m;
n++;
goto els;
}
}
else
{
els:
m=m+i-T[i];
if(i>0) i=T[i];
}
}
}
int main()
{
fin.getline(w,Max);
fin.getline(s,Max);
ls=strlen(s);
lw=strlen(w);
KMP();
fout<<n<<'\n';
n=min(n,1000);
for(int i=0;i<n;i++)
fout<<h[i]<<' ';
fout<<'\n';
}