Pagini recente » Cod sursa (job #1624598) | Cod sursa (job #2218185) | Cod sursa (job #1540773) | Cod sursa (job #1672907) | Cod sursa (job #2647691)
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000000], b[2000000];
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int n, m;
int matches[1000];
fgets(a+1, sizeof(a), stdin);
fgets(b+1, sizeof(b), stdin);
n = strlen(a+1);
if (a[n] == '\n') {
a[n] = 0;
--n;
}
m = strlen(b+1);
if (b[m] == '\n') {
b[m] = 0;
--m;
}
int pi[n+1];
pi[1] = 1;
int k=0;
for(int i=2; i<=n; ++i) {
while(k > 0 && a[k+1] != a[i])
k = pi[k];
if (a[k+1] == a[i])
++k;
pi[i] = k;
}
int q=0, matchno = 0;
for(int i=1; i<=m; ++i) {
while (q>0 && a[q+1] != b[i])
q = pi[q];
if (a[q+1] == b[i])
++q;
if (q == n) {
if (matchno < 1000)
matches[matchno] = i - n;
++matchno;
q = pi[n];
}
}
printf("%d\n", matchno);
for(int i=0; i<matchno && i < 1000; ++i)
printf("%d ", matches[i]);
return 0;
}