Pagini recente » Cod sursa (job #2903000) | Cod sursa (job #2122888) | Cod sursa (job #26086) | Cod sursa (job #2998466) | Cod sursa (job #2056423)
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define NMax 2000001
int i,M,n,N,j,pi[NMax],pos[NMax];
char a[NMax],b[NMax];
void prefix()
{
int i,q=0;
for(i=2,pi[1]=0;i<=M;++i)
{
while(q && a[q+1]!=a[i]) q=pi[q];
if(a[q+1]==a[i]) ++q;
pi[i]=q;
}
}
void aaa()
{
int i,q=0;
for(i=1;i<=N;++i)
{
while(q && a[q+1]!=b[i]) q=pi[q];
if(a[q+1]==b[i]) q++;
if(q==M)
{
q=pi[M];
n++;
pos[n]=i-M;
}
}
g<<n<<'\n';
if(n>=1000)
n=1000;
for(i=1;i<=n;++i)
g<<pos[i]<<' ';
}
int main()
{
f.getline(a,NMax);
f.getline(b,NMax);
M=strlen(a);
N=strlen(b);
for(i=M;i;i--) a[i]=a[i-1];a[0]=' ';
for(i=N;i;i--) b[i]=b[i-1];b[0]=' ';
prefix();
aaa();
f.close();g.close();
return 0;
}