Pagini recente » Cod sursa (job #1646171) | Cod sursa (job #2535559) | Cod sursa (job #819113) | Cod sursa (job #1801573) | Cod sursa (job #2164630)
#include <iostream>
#include <fstream>
#include <cstring>
#define N 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int L[N],d[N];
char T[N],P[N];
int n,m;
void Precalc()
{
int i,k=0;
L[0]=0;
for(i=1;i<m;++i)
{
if(P[i]==P[k])k++;
else
{
while(k>0 && P[i]!=P[k])k=L[k-1];
if(P[i]==P[k])k++;
}
L[i]=k;
}
}
void KMP()
{
int i,k=0;
for(i=0;i<n;++i)
{
if(T[i]==P[k])
k++;
else
{
while(k>0 && T[i]!=P[k])k=L[k-1];
if(T[i]==P[k])k++;
}
d[i]=k;
}
}
int main()
{
int i;
fin>>T>>P;
n=strlen(T);
m=strlen(P);
Precalc();
KMP();int ct=0;
for(i=0;i<n;++i)if(d[i]==m)ct++;
fout<<ct<<"\n";
for(i=0;i<n;++i)if(d[i]==m)fout<<i-m+1<<" ";
return 0;
}