Pagini recente » Cod sursa (job #900637) | Cod sursa (job #2167546)
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char t[N],p[N];
int L[N],n,m,d[N],ct,s;
void Precalculare(){
int i=1,k=0;
L[0]=0;
while(i<m)
{
if(p[i]==p[k]) L[i]=++k, i++;
else
if(k>0) k=L[k-1];
else L[i]=0, i++;
}
}
void KMP(){
int i=0,k=0;
while(i<n)
{
if(t[i]==p[k]) i++,k++;
if(k==m) d[++ct]=i-k, k=L[k-1];
else if(i<n && t[i]!=p[k])
if(k>0) k=L[k-1];
else i++;
}
fout<<ct<<'\n';
for(i=1; i<=ct; i++) fout<<d[i]<<' ';
}
int main()
{
fin>>p>>t;
fin.close();
m=strlen(p);
n=strlen(t);
Precalculare();
KMP();
fout.close();
return 0;
}