Pagini recente » Cod sursa (job #3032264) | Cod sursa (job #1205189) | Cod sursa (job #1797326) | Cod sursa (job #595737) | Cod sursa (job #2216884)
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define NMAX 2000005
int match[NMAX], z[NMAX], n, m, ans, answers[NMAX];
char p[NMAX], s[NMAX];
void PreprocesarePi() {
int i, stanga = 0, dreapta = 0, poz, nr;
for(i = 2; i <= m; i++) {
if(i > dreapta) {
poz = 1;
while(i + poz - 1 <= m && p[poz] == p[i + poz - 1])
poz++;
poz--; z[i] = poz;
if(poz) {
dreapta = i + poz - 1;
stanga = i;
}
continue;
}
nr = i - stanga + 1;
if(i + z[nr] - 1 < dreapta)
z[i] = z[nr];
else {
z[i] = dreapta - i + 1;
stanga = i;
while(dreapta < m && p[z[i] + 1] == p[dreapta + 1]) {
z[i]++;
dreapta++;
}
}
}
}
void solve() {
int i, stanga = 0, dreapta = 0, poz, nr;
memset(match, 0, sizeof(match));
for(i = 1; i <= n; i++) {
if(i > dreapta) {
poz = 1;
while(poz <= m && i + poz - 1 <= n && p[poz] == s[i + poz - 1])
poz++;
poz--; match[i] = poz;
if(poz) {
dreapta = i + poz - 1;
stanga = i;
}
if(match[i] == m) {
answers[++ans] = i;
}
continue;
}
nr = i - stanga + 1;
if(i + z[nr] - 1 < dreapta)
match[i] = z[nr];
else {
match[i] = dreapta - i + 1;
stanga = i;
while(match[i] < m && dreapta < n && p[match[i] + 1] == s[dreapta + 1]) {
match[i]++;
dreapta++;
}
}
if(match[i] == m) {
answers[++ans] = i;
}
}
}
int main () {
int aux,i,p1,p2;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s", p + 1); m = strlen(p + 1);
scanf("%s", s + 1); n = strlen(s + 1);
PreprocesarePi();
solve();
printf("%d\n", ans);
if(ans > 1000) {
ans = 1000;
}
for(int i = 1; i <= ans; i++) {
printf("%d ", answers[i] - 1);
}
printf("\n");
return 0;
}