Pagini recente » Cod sursa (job #1539334) | Cod sursa (job #1393733) | Cod sursa (job #2817331) | Cod sursa (job #2338945) | Cod sursa (job #552382)
Cod sursa(job #552382)
//kmp
#include <fstream>
#include <string.h>
#include <stdio.h>
using namespace std;
char p[2000005], t[2000005];
int a[2000005], b[2000005], n, m, k=0;
void citire()
{
freopen("strmatch.in", "r", stdin);
scanf("%s", p);
scanf("%s", t);
m=strlen(p);
n=strlen(t);
}
void kmp1()
{
int i=0, j=-1;
b[i]=j;
while (i<m)
{
while (j>=0 && p[i]!=p[j])
j=b[j];
i++;
j++;
b[i]=j;
}
}
void kmp2()
{
int i=0, j=0;
while (i<n)
{
while (j>=0 && t[i]!=p[j])
j=b[j];
i++;
j++;
if (j==m)
{
k++;
a[k]=(i-j);
j=b[j];
}
}
}
void afisare()
{
freopen("strmatch.out","w",stdout);
printf("%d\n", k);
for(int i=1; i<=k && i<=1000; i++)
printf("%d ",a[i]);
}
int main()
{
citire();
kmp1();
kmp2();
afisare();
return 0;
}