Pagini recente » Cod sursa (job #1435966) | Cod sursa (job #3153690) | Cod sursa (job #2799) | Cod sursa (job #1852595) | Cod sursa (job #1896689)
#include <iostream>
#include <fstream>
#include <cstring>
#define NMax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int m, n;
char a[NMax],b[NMax];
int pi[NMax],pos[1010];
inline int minim(int x,int y)
{
if(x>y)return y;
else return x;
}
void make_prefix()
{
int i,q=0;
pi[1]=0;
for (i=2;i<=m;++i)
{
while (q&&a[q+1]!=a[i])q=pi[q];
if (a[q+1]==a[i])++q;
pi[i]=q;
}
}
int main()
{
int i,q=0,nr=0;
f>>a;m=strlen(a);
f>>b;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]=' ';
make_prefix();
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];
++nr;
if (nr<=1000)pos[nr]=i-m;
}
}
g<<nr<<'\n';
for (i=1;i<=minim(nr,1000);++i)
g<<pos[i]<<" ";
return 0;
}