Pagini recente » Cod sursa (job #1031729) | Cod sursa (job #1874341) | Cod sursa (job #171548) | Cod sursa (job #2153414) | Cod sursa (job #415238)
Cod sursa(job #415238)
#include<cstdio>
#include<cstring>
const char in[]="strmatch.in", out[]="strmatch.out";
const int N = 2000005;
const int M = 1000;
char a[N], b[N];
int p[N], v[M+5], n, m, k, nr;
int main()
{
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%s %s", a, b);
n = strlen(a) ;m = strlen(b) ;
p[0]=p[1]=0;
k=0;
int i;
for(i = 1 ; i < n; ++i)
{
while(k > 0 && a[i] != a[k]) k = p[k];
if(a[i] == a[k]) ++k;
p[i + 1] = k;
}
k = 0;
for(i = 0; i < m; ++i)
{
while(k > 0 && a[k] != b[i])k = p[k];
if(a[k] == b[i]) ++k;
if( k == n)
{
if( nr < M )v[ nr ] = i - n +1 ;
++nr;
k = p[ k ];
}
}
printf("%d\n",nr);
for(int i = 0; i <= (nr < M ? nr : M ); ++i)
printf("%d ", v[i]);
return 0;
}