Pagini recente » Cod sursa (job #97717) | Cod sursa (job #686642) | Cod sursa (job #1208478) | Cod sursa (job #1380748) | Cod sursa (job #2274467)
#include <iostream>
#include <cstring>
#include <fstream>
#define Nmax 200005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int p[Nmax],v[Nmax];
void model(char b[Nmax],int lb)
{
int j;
j=0;
for(int i=1;i<lb;i++)
{
while(j>0&&b[i]!=b[j])
j=p[j-1];
if(b[i]==b[j])
{p[i]=j+1;
j=j+1;
}
}
}
void kmp(char b[Nmax],char a[Nmax],int &nr,int la,int lb)
{
int j=0;
for(int i=0;i<la;i++)
{
while (j>0&&a[i]!=b[j])
j=p[j-1];
if(a[i]==b[j])
{
j=j+1;
}
if(j==strlen(b))
{
nr++;
if(nr<=1000)
v[nr]=i-lb+1;
}
}
}
int main()
{
char a[Nmax],b[Nmax];
int nr=0,la,lb;
f>>a>>b;
la=strlen(a);
lb=strlen(b);
model(b,lb);
kmp(b,a,nr,la,lb);
g<<nr<<endl;
for(int i=1;i<=nr&&i<=1000;i++)
g<<v[i]<<" ";
return 0;
}