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