Pagini recente » Cod sursa (job #223705) | Cod sursa (job #112415) | Cod sursa (job #3250929) | Cod sursa (job #2117066) | Cod sursa (job #2335617)
///strmatch pe infoarena
#define LMAX 2000005
#include <cstdio>
#include <cstring>
using namespace std;
char s[LMAX]; /// stringul in care cautam
char p[LMAX]; /// stringul cautat
int P[LMAX]; /// Sirul cu prefixe
int fin[1005];
int n, m, o;
void formare_Prefixe()
{
int i=0, j=-1;
P[0] = -1;
while(i < m)
{
while(j >= 0 && p[i] != p[j])
j = P[j];
i++;
j++;
P[i] = j;
}
}
void kmp()
{
int i=0, j=0;
while(i < n)
{
while(j >= 0 && s[i] != p[j])
j = P[j];
i++;
j++;
if(j == m)
{
j = P[j];
o++;
if(o <= 1000)
fin[o] = i-m;
}
}
}
void afis()
{
printf("%d\n", o);
if(o > 1000)
o = 1000;
for(int i=1; i<=o; i++)
printf("%d ", fin[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s\n%s", p, s);
m = strlen(p);
n = strlen(s);
formare_Prefixe();
kmp();
afis();
return 0;
}