Pagini recente » Cod sursa (job #2693524) | Cod sursa (job #1613840) | Cod sursa (job #2489720) | Cod sursa (job #178755) | Cod sursa (job #554014)
Cod sursa(job #554014)
#include <cstdio>
#include <string>
using namespace std;
#define FIN "strmatch.in"
#define FOUT "strmatch.out"
#define nmax 2000005
char t[nmax], p[nmax];
long l[nmax], n, m, total, sol[1000];
void citire()
{
freopen(FIN,"r",stdin);
scanf("%s %s", p+1, t+1); n = strlen(t+1); m = strlen(p+1);
}
void afisare()
{
freopen(FOUT,"w",stdout);
printf("%ld\n", total);
for(int i=0; i<(total<1000 ? total:1000); i++)
printf("%ld ", sol[i]);
}
void prefix()
{
int k = 0;
for (int i=2; i<=m; i++)
{
while (k && p[k+1] != p[i])
k = l[k];
if (p[k+1] == p[i])
k++;
l[i] = k;
}
}
void kmp()
{
int k = 0;
for (int i=1; i<=n; i++)
{
while (k && p[k+1] != t[i])
k = l[k];
if (p[k+1] == t[i])
k++;
if (k == m)
{
k = l[m];
if(total < 1000)
sol[total] = i-m;
total++;
}
}
}
int main()
{
citire();
prefix();
kmp();
afisare();
return 0;
}