Pagini recente » Cod sursa (job #1653845) | Cod sursa (job #1488804) | Cod sursa (job #1530076) | Cod sursa (job #2057030) | Cod sursa (job #1744981)
#include <stdio.h>
#include <string.h>
#define minim(a, b) ((a < b) ? a : b)
#define maxim(a, b) ((a > b) ? a : b)
#define NMax 2000005
int t[NMax];
char s[NMax], w[NMax];
int n, m, sol[1024], sl;
//t[x] = how much w needs to pad left to continue the checl
void table()
{
int pos = 1;
int cnd = 0;
while (pos<m)
{
if(w[pos] == w[cnd])
t[pos++] = ++cnd;
else if(cnd>0)
cnd = t[cnd];
else
pos++;
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(w, sizeof(w), stdin);
fgets(s, sizeof(s), stdin);
n = strlen(s) - 1;
m = strlen(w) - 1;
//i for s, p for w
for(int i=0, p=0; i + p <= n;)
{
if(s[i+p] == w[p])
{
if(p == m - 1)
{
sl++;
if(sl<=1000)
sol[sl] = i;
p = t[p];
i += maxim(p, 1);
}
else p++;
}
else
{
p = t[p];
i += maxim(p, 1);
}
}
printf("%d\n", sl);
for (int i = 1; i <= sl; i++)
{
printf("%d ", sol[i]);
}
return 0;
}