Pagini recente » Cod sursa (job #3194226) | Cod sursa (job #1455710) | Cod sursa (job #451222) | Cod sursa (job #250465) | Cod sursa (job #1158999)
#include <fstream>
#include <cstring>
#define DIM 2000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, m, i, j, p[DIM], v[DIM], nr, q;
char a[DIM], b[DIM];
void prefix(){
p[1]=0;
for(i=2; i<=m; i++)
{
q=p[i]-1;
while(b[i]!=b[q+1] && q!=0)
q=p[q];
if(b[i]==b[q+1])
p[i]=q+1;
else
p[i]=0;
}
}
void kmp(){
q=0;
for(i=1; i<=n; i++)
{
while(a[i]!=b[q+1] && q!=0)
q=p[q];
if(a[i]==b[q+1])
q++;
if(q==m)
{
v[++nr]=i-m;
q=p[q];
}
}
}
int main(){
f.get(b+1, DIM);
f.get();
f.get(a+1, DIM);
n=strlen(a+1);
m=strlen(b+1);
prefix();
kmp();
g<<nr<<"\n";
for(i=1; i<=nr; i++)
g<<v[i]<<' ';
g<<"\n";
return 0;
}