Pagini recente » Cod sursa (job #2354302) | Cod sursa (job #2501864) | Cod sursa (job #963120) | Cod sursa (job #2438049) | Cod sursa (job #2056398)
#include <fstream>
#include <string.h>
using namespace std;
ifstream f("kmp.in");
ofstream g("kmp.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)
// if(pos[i]!=0)
g<<pos[i]<<' ';
g<<'\n';
}
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();
// for(i=1;i<=M;i++)
// g<<pi[i];
aaa();
f.close();g.close();
return 0;
}