Pagini recente » Cod sursa (job #2161409) | Cod sursa (job #564865) | Cod sursa (job #1412660) | Cod sursa (job #1972435) | Cod sursa (job #2316312)
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char a[2000010],b[2000010];
int S[1010],prefix[2000010];
int n,m,L,i,nr;
int main(){
fin>>a+1>>b+1;
n=strlen(a+1);
m=strlen(b+1);
prefix[1]=0;
L=0;
///prefix
for(i=2;i<=n;i++){
while(L>0 && a[L+1]!=a[i])
L=prefix[L];
if(a[L+1]==a[i])
L++;
prefix[i]=L;
}
///potrivire
L=0;
for(i=1;i<=m;i++){
while(L>0 && a[L+1]!=b[i])
L=prefix[L];
if(a[L+1]==b[i])
L++;
if(L==n){
nr++;
if(nr<=1000)
S[nr]= i-n;
L=prefix[L];
}
}
fout<<nr<<"\n";
if(nr>1000)
nr=1000;
for(i=1;i<=nr;i++){
fout<<S[i]<<" ";
}
return 0;
}