Pagini recente » Cod sursa (job #2862240) | Cod sursa (job #944653) | Cod sursa (job #381662) | Cod sursa (job #1433542) | Cod sursa (job #2552987)
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
void Citire();
void Pref();
void KMP();
char T[N],P[N];
int n,m,k;
int a[N],urm[N];
int main()
{
Citire();
KMP();
fout<<k<<'\n';
if(k>1000) k=1000;
for(int i=1;i<=k;++i)
fout<<a[i]<<' ';
return 0;
}
void Citire(){
fin.getline(P,N);
fin.getline(T,N);
n=strlen(P);
m=strlen(T);
}
void Pref(){
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;
// }
//
for(int i=1;i<n;++i){
int i2=i;
for(;i<N and P[i]==P[i-i2]; ++i)
urm[i]=i-i2+1;
if(i2!=i) --i;
}
// for(int i=0;i<n;++i)
// cout<<urm[i]<<" ";
}
void KMP()
{
Pref();
int q=0;
for(int i=0;i<m;++i)
{
while(q>0 && P[q]!=T[i]) q=urm[q-1];
if(P[q]==T[i]) ++q;
if(q==n) a[++k]=i-n+1;
}
}