Pagini recente » Cod sursa (job #2518863) | Cod sursa (job #1287696) | Atasamentele paginii muzica | Cod sursa (job #2161654) | Cod sursa (job #886307)
Cod sursa(job #886307)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>rez;
int p[200005];
char A[200005],B[200005];
int n,i,j,k,m,t;
void prefix()
{
k=0;p[k]=0;
for (i=2;i<=n;i++)
{
while (k && A[k+1]!=A[i]) k=p[k];
if (A[k+1]==A[i]) k++;
p[i]=k;
}
}
void KMP()
{
k=0;
for (i=1;i<=m;i++)
{
while (k && A[k+1]!=B[i]) k=p[k];
if (A[k+1]==B[i]) k++;
if (k==n && rez.size()<1000) rez.push_back(i-n);
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(A+1);
gets(B+1);
n=strlen(A+1);
m=strlen(B+1);
prefix();
KMP();
printf("%d\n",rez.size());
k=rez.size();
for (i=0;i<k;i++) printf("%d ",rez[i]);
return 0;
}