Pagini recente » Cod sursa (job #863055) | Cod sursa (job #1731605) | Cod sursa (job #1305421) | Cod sursa (job #2925467) | Cod sursa (job #2550723)
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char T[N],P[N];
int a[N]; ///memoram pozitiile in a
int urm[N];
int n,m,k;
void citire()
{fin>>P>>T;
n=strlen(P);
m=strlen(T);
}
void prefix()
{int j=0;
for(int i=1;i<n;++i)
{while(j>0 && P[i]!=P[j])
j=urm[j-1];
if(P[i]==P[j])
j++;
urm[i]=j;
}
}
void kmp()
{int q=0;
for(int i=0;i<m;++i)
{while(q>0 && P[q]!=T[i])
q=urm[q-1];
if(T[i]==P[q])
q++;
if(q==n)
a[k++]=i-n+1;
}
}
int main()
{citire();
prefix();
kmp();
if(k>1000) k=1000;
fout<<k<<"\n";
for(int i=0;i<k;++i)
fout<<a[i]<<" ";
return 0;
}