Pagini recente » Cod sursa (job #2901052) | Cod sursa (job #933661)
Cod sursa(job #933661)
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
#define NMAX 2000002
char a[NMAX],b[NMAX];
int v[NMAX],p[NMAX];
void prefix(int n)
{
int i,q;
v[1]=0;
q=0;
for(i=2;i<=n;i++) {
while(q && a[q+1]!=a[i])
q=v[q];
if(a[q+1]==a[i])
q++;
v[i]=q;
}
}
int main ()
{
int i,q,n,m,l;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>(a+1)>>(b+1);
f.close();
n=strlen(a+1);
m=strlen(b+1);
prefix(n);
l=0;
q=0;
for(i=1;i<=m;i++) {
while(q && b[i]!=a[q+1])
q=v[q];
if(b[i]==a[q+1])
q++;
if(q==n) {
q=v[n];
l++;
if(l<=1000)
p[l]=i-n;
}
}
g<<l<<'\n';
for(i=1;i<=l && i<=1000;i++)
g<<p[i]<<" ";
g.close();
return 0;
}