Pagini recente » Rating Mihalcea Simoiu Agatha (Agatha01) | Cod sursa (job #1799233) | Cod sursa (job #2521870) | Monitorul de evaluare | Cod sursa (job #2017504)
#include <bits/stdc++.h>
using namespace std;
char p[2000005], t[2000005];
int pi[2000005], sol[2000005];
inline void make_prefix(int m){
int k = 0;
pi[1] = 0;
for(int q = 2; q <= m ; ++q){
while(k > 0 && p[k + 1] != p[q])
k = pi[k];
if(p[k + 1] == p[q]) ++k;
pi[q] = k;
}
}
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", p + 1);
scanf("%s", t + 1);
int m = strlen(p + 1);
int n = strlen(t + 1);
make_prefix(m);
int q = 0, nr = 0;
for(int i = 1; i <= n ; ++i){
while(q > 0 && t[i] != p[q + 1])
q = pi[q];
if(t[i] == p[q + 1]) ++q;
if(q == m){
q = pi[m];
++nr;
if(nr <= 1000)
sol[nr] = i - m;
}
}
printf("%d\n", nr);
for(int i = 1; i <= nr ; ++i)
printf("%d ", sol[i]);
return 0;
}