Pagini recente » Cod sursa (job #1791469) | Cod sursa (job #159912) | Cod sursa (job #2795529) | Cod sursa (job #2632774) | Cod sursa (job #1028438)
#include <stdio.h>
#include <string.h>
#define mx 2000010
long pi[mx+1];
long v[1024];
char s1[mx+2],s2[mx+2];
int prefix(const char *s) {
int k = 0, i = 0;
const char *start = s;
for (i = 2, s += 2; *s; i++, s++) {
for (; k && !(start[k + 1] == *s); k = pi[k + 1]);
if (start[k + 1] == *s)
k++;
pi[i] = k;
}
return i - 2;
}
int h, i;
void kmp(const char *s, const char *f) {
int n = prefix(--s);
int k = 0, i = 0;
for (i = 0; *f; i++, f++) {
for (; k && !(s[k + 1] == *f); k = pi[k]);
if (s[k + 1] == *f)
k++;
if (k == n) {
h++;
k = pi[k];
if (h<=1000)
v[h]=i-n + 1;
}
}
}
int main(void)
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout); fgets(s1,mx,stdin);
fgets(s2,mx,stdin);
kmp(s1, s2);
printf("%ld\n",h);
if (h>1000)
h=1000;
for (i=1; i<=h; i++)
printf("%ld ",v[i]);
fclose(stdin);
fclose(stdout);
return 0;
}