Pagini recente » Cod sursa (job #2322434) | Cod sursa (job #712605) | Cod sursa (job #2684742) | Cod sursa (job #3139628) | Cod sursa (job #1631981)
#include <bits/stdc++.h>
using namespace std;
char s[4000100];
int z[4000100];
int sol[1100];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(s + 1);
int m = strlen(s + 1);
int n = m;
int res = 0;
s[++n] = '$';
gets(s + n + 1);
n = strlen(s + 1);
int l = 0, r = 0;
for (int i = 2; i <= n; ++i) {
if (i >= r) {
while (i + z[i] <= n && s[i + z[i]] == s[z[i] + 1])
++z[i];
l = i;
r = i + z[i] - 1;
} else {
int i2 = i - l + 1;
z[i] = z[i2];
if (i + z[i] - 1 >= r) {
z[i] = r - i + 1;
while (i + z[i] <= n && s[i + z[i]] == s[z[i] + 1])
++z[i];
l = i;
r = i + z[i] - 1;
}
}
if (z[i] == m) {
++res;
if (res <= 1000)
sol[res] = i - m - 2;
}
}
printf("%d\n", res);
for (int i = 1; i <= min(res, 1000); ++i)
printf("%d ", sol[i]);
return 0;
}