Pagini recente » Cod sursa (job #2095916) | Cod sursa (job #37493) | Cod sursa (job #616160) | Cod sursa (job #3151602) | Cod sursa (job #2732797)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX = 2000005;
char a[2*NMAX],b[NMAX];
int z[2*NMAX],rasp[2*NMAX];
int main()
{
fin >> (a+1);
fin >> (b+1);
int n=strlen(a+1),m=strlen(b+1);
int aux=n;
a[n+1]='$';
for(int i=n+2;i<=n+m+1;i++) a[i]=b[i-n-1];
n=n+m+1;
int L=0,R=0;
for(int i=2;i<=n;i++){
if(i<=R) z[i]=min(z[i-L+1],R-i+1);
while(i+z[i]<=n and a[i+z[i]]==a[1+z[i]]) z[i]++;
if(i+z[i]-1>R){
R=i+z[i]-1;
L=i;
}
}
int dim=0;
for(int i=aux+2;i<=n;i++){
if(z[i]==aux){
rasp[++dim]=i-aux-2;
}
}
fout << dim << '\n';
for(int i=1;i<=dim and i<=1000;i++)
fout << rasp[i] << ' ';
return 0;
}