Pagini recente » Cod sursa (job #425195) | Cod sursa (job #699935) | Cod sursa (job #3220078) | Cod sursa (job #519369) | Cod sursa (job #1740402)
#include<fstream>
#include<string.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,i,j,k,potrivire[2000001],nr,coada[2000001];
char a[2000001],b[2000001];
void pi(){
int k=-1,i;
potrivire[0]=0;
for (i=1;i<n;i++){
while(k>0 && a[k+1]!=a[i]) k=potrivire[k];
if (a[k+1]==a[i]) k++;
potrivire[i]=k;
}
}
int main(){
fin.get(a,2000001,'\n');
fin.get();
fin.get(b,2000001,'\n');
fin.close();
n=strlen(a);
m=strlen(b);
pi();
k=-1;
for (i=0;i<m;i++){
while(k>0 && a[k+1]!=b[i]) k=potrivire[k];
if (a[k+1]==b[i]) k++;
if (k==n-1){
nr++;
if (nr<=1000) coada[nr]=i-n+1;
}
}
fout<<nr<<'\n';
if (nr<=1000)
for (i=1;i<=nr;i++)
fout<<coada[i]<<" ";
else
for (i=1;i<=1000;i++)
fout<<coada[i]<<" ";
fout.close();
return 0;
}