Pagini recente » Cod sursa (job #2051971) | Cod sursa (job #183235) | Cod sursa (job #28185) | Cod sursa (job #1035089) | Cod sursa (job #2717821)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int N=2000002;
const int P=1000;
char a[N],b[N],c[N];
int pi[N];
int main()
{
cin>>(1+a)>>(1+b);
int lung=0,m=strlen(1+a),n=strlen(1+b);
pi[1]=0;
for (int i=2;i<=m;i++){
while (lung>0 && a[i]!=a[lung+1]){
lung=pi[lung];
}
if (a[i]==a[lung+1]){
lung++;
}
pi[i]=lung;
}
lung=0;
int nr=0;
for (int i=1;i<=n;i++){
while (lung>0 && b[i]!=a[lung+1]){
lung=pi[lung];
}
if (b[i]==a[lung+1]){
lung++;
}
if (lung==m){
c[i-1]=1;
nr++;
}
}
cout<<nr<<"\n";
nr=P;
for (int i=0;i<n && nr>0;i++){
if (c[i]){
cout<<i-m+1<<" ";
nr--;
}
}
return 0;
}