Pagini recente » Cod sursa (job #427654) | Cod sursa (job #615633) | Cod sursa (job #1189071) | Cod sursa (job #1241034) | Cod sursa (job #1241037)
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int pi[2000001];
char a[2000002], b[2000002];
int ans[1005], nr, la, lb;
// k = cate caractere am potrivit (de la 0 la k-1)
void prefix() {
int i, k = 0;
for(i = 1; i < la; i++) {
while(k > 0 && a[i] != a[k]) {
k = pi[k-1];
}
if(a[i] == a[k]) {
k++;
}
pi[i] = k;
}
}
void match() {
int i, k = 0;
for(i = 0; i < lb; i++) {
while(k > 0 && b[i] != a[k]) {
k = pi[k-1];
}
if(b[i] == a[k]) {
k++;
}
if(k == la) {
if(nr < 1000) {
ans[nr] = i-k+1;
}
nr++;
k = pi[k-1];
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int i, to;
scanf("%s %s", a, b);
la = strlen(a);
lb = strlen(b);
prefix();
match();
printf("%d\n", nr);
to = (nr > 1000) ? 1000 : nr;
for(i = 0; i < to; i++) {
printf("%d ", ans[i]);
}
return 0;
}