Pagini recente » Cod sursa (job #643878) | Cod sursa (job #727865) | Cod sursa (job #1773823) | Cod sursa (job #929457) | Cod sursa (job #1740426)
#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=0,i;
potrivire[1]=0;
for (i=2;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);
for (i=n;i>=1;i--)
a[i]=a[i-1];
for (i=m;i>=1;i--)
b[i]=b[i-1];
pi();
k=0;
for (i=1;i<=m;i++){
while(k>0 && a[k+1]!=b[i]) k=potrivire[k];
if (a[k+1]==b[i]) k++;
if (k==n){
k=potrivire[n];
nr++;
if (nr<=1000) coada[nr]=i-n;
}
}
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;
}