Pagini recente » Cod sursa (job #542497) | Cod sursa (job #3151892) | Cod sursa (job #2045847) | Cod sursa (job #1294682) | Cod sursa (job #796627)
Cod sursa(job #796627)
#include <cstdio>
#include <cstring>
#define minim(a,b)((a < b) ? a:b)
#define N 20000001
char a[N], b[N];
int m, n, nr, pi[N], q = 0, pos[1024];
void prefix(){
pi[1] = 0;
for(int i=2;i<=n;i++)
{
while(q>0 && a[q+1] != a[i])
q = pi[q];
if(a[q+1] == a[i])
q++;
pi[i] = q;
}
}
void kmp()
{
n=strlen(a),m=strlen(b);
for (int i = n; i; i--)
a[i] = a[i-1];
a[0] = ' ';
for (int i = m; i; i--)
b[i] = b[i-1];
b[0] = ' ';
prefix();
for(int i=0;i<=m;i++)
{
while(q>0 && a[q+1]!= b[i])
q = pi[q];
if(a[q+1] == b[i])
q++;
if(q == n)
{
q = pi[n];
nr++;
if(nr<=1000)
pos[nr] = i-n;
}
}
printf("%d\n", nr);
for(int i = 1; i <= minim(nr,1000); i++)
printf("%d ",pos[i]);
printf("\n");
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s", a, b);
kmp();
return 0;
}