Pagini recente » Cod sursa (job #539028) | Cod sursa (job #2247084) | Cod sursa (job #1588792) | Cod sursa (job #1818391) | Cod sursa (job #2266731)
#include <bits/stdc++.h>
using namespace std;
char s[4000020];
int z[4000020];
int rez[1010];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", s + 1);
int n = strlen(s + 1), lrez = 0, m;
m = n;
s[n + 1] = 1;
scanf("%s", s + n + 2);
n += strlen(s + n + 2);
int l = 0, r = 0;
z[1] = 0;
for(int i = 2; i <= n; i++) {
if(i <= r) {
z[i] = min(z[i - l], r - i + 1);
}
while(i + z[i] - 1 <= n && s[i + z[i]] == s[z[i] + 1]) {
z[i]++;
}
if(i + z[i] - 1 >= r) {
r = i + z[i] - 1;
l = i;
}
if(z[i] == m) {
lrez++;
if(lrez <= 1000)
rez[lrez] = i - m - 2;
}
}
printf("%d\n", lrez);
for(int i = 1; i <= min(1000, lrez); i++)
printf("%d ", rez[i]);
return 0;
}