Pagini recente » Cod sursa (job #2902212) | Cod sursa (job #560975) | Cod sursa (job #1220751) | Cod sursa (job #2422533) | Cod sursa (job #504887)
Cod sursa(job #504887)
#include <cstdio>
using namespace std;
#define k 2000001
char a[k],b[k];
int p[k],v[1<<10];
int n,m,mn;
void read (){
freopen ("strmatch.in","r",stdin);
fgets(a, sizeof(a) , stdin);
fgets(b, sizeof(b) , stdin);
for(;(a[m]>='A'&&a[m]<='Z')||(a[m]<='z'&&a[m]>='a')||(a[m]>='0'&&a[m]<='9');++m);
for(;(b[n]>='A'&&b[n]<='Z')||(b[n]<='z'&&b[n]>='a')||(b[n]>='0'&&b[n]<='9');++n);
for(int i=m;i;--i)
a[i]=a[i-1];
a[0]=' ';
for(int i=n;i;--i)
b[i]=b[i-1];
b[0]=' ';
}
void solve (){
int q=0,i;
for (p[1] = 0,i=2; i <= m; ++i)
{
while (q && a[q+1] != a[i])
q = p[q];
if (a[q+1] == a[i])
++q;
p[i] = q;
}
q=0;
for(i=1;i<=n;++i){
while(q&&a[q+1]!=b[i])
q=p[q];
if(a[q+1]==b[i])
++q;
if(q==m){
q=p[m];
++mn;
if(mn<=1000)
v[mn]=i-m;
}
}
}
int inline min (int x,int y){
return (x < y) ? x : y;
}
void write (int kk){
freopen ("strmatch.out","w",stdout);
printf("%d\n",mn);
for(int i=1;i<=kk;++i)
printf("%d ",v[i]);
printf("\n");
}
int main ()
{
read ();
solve ();
write (min(mn,1000));
return 0;}