Pagini recente » Cod sursa (job #766006) | Cod sursa (job #2904891) | Cod sursa (job #340322) | Cod sursa (job #519904) | Cod sursa (job #1921671)
#include <iostream>
#include <fstream>
#include <cstring>
#define nmax 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m;
char a[nmax], b[nmax];
int pos[1024], p[nmax];
void prefix()
{
int i, q=0;
for(i=2, p[1]=0; i<=n; ++i)
{
while(q && a[q+1]!=a[i]) q=p[q];
if(a[q+1]==a[i]) ++q;
p[i]=q;
}
}
int main()
{
f>>a>>b;
n=strlen(a);
m=strlen(b);
for(int i=n; i; --i) a[i]=a[i-1];
a[0]=' ';
for(int i=m; i; --i) b[i]=b[i-1];
b[0]=' ';
prefix();
int q=0, nr=0;
for(int i=1; i<=m; ++i)
{
while(q && a[q+1]!=b[i]) q=p[q];
if(a[q+1]==b[i]) ++q;
if(q==n)
{
q=p[n];
++nr;
if(nr<=1000)
{
pos[nr]=i-n;
}
}
}
g<<nr<<"\n";
for(int i=1; i<=min(nr, 1000); ++i)
{
g<<pos[i]<<" ";
}
return 0;
}