Pagini recente » Cod sursa (job #158562) | Cod sursa (job #1028181) | Cod sursa (job #173696) | Cod sursa (job #1582285) | Cod sursa (job #979585)
Cod sursa(job #979585)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int* table(char *s) {
int n = strlen(s), pos = 2, cnd = 0;
int *t = malloc((n + 1) * sizeof(int));
t[0] = -1;
t[1] = 0;
while(pos < n) {
if (s[pos - 1] == s[cnd]) {
cnd++;
t[pos] = cnd;
pos++;
} else if (cnd > 0) {
cnd = t[cnd];
} else {
t[pos] = 0;
pos++;
}
}
return t;
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
char *str = malloc(2000000);
int r = 0;
int results[2000000];
char *s, *p;
scanf("%s", str);
p = strdup(str);
scanf("%s", str);
s = strdup(str);
free(str);
int *t = table(p);
int i, m, l = strlen(s);
i = 0, m = 0;
while (i + m < l) {
if (p[i] == s[m + i]) {
if (i == strlen(p) - 1) {
results[r++] = m;
i = 0;
m++;
} else {
i++;
}
} else {
m += i - t[i];
if (t[i] < 0)
i = 0;
else
i = t[i];
}
}
printf("%d\n", r);
for (i = 0; i < r; i++)
printf("%d ", results[i]);
return 0;
}