Pagini recente » Cod sursa (job #1783090) | Cod sursa (job #2058079) | Istoria paginii utilizator/oana_tosa15 | Cod sursa (job #1537597) | Cod sursa (job #1726440)
///KMP
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2000005;
int pi[NMAX],
mt[NMAX];
char p[NMAX],
t[NMAX];
int main(void) {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int n, m, q, ans;
scanf("%s%s",p+1,t+1);
n = strlen(t+1);
m = strlen(p+1);
ans = 0;
if(n < m) {
printf("%d\n",0);
fclose(stdin);
fclose(stdout);
}
pi[1] = 0;
for(int i=2, k=0; i<=m; ++i) {
while(k>0 && p[k+1]!=p[i])
k = pi[k];
if(p[k+1]==p[i])
++k;
pi[i] = k;
}
q = 0;
for(int i=1; i<=n; ++i) {
while(q>0 && p[q+1]!=t[i])
q = pi[q];
if(p[q+1]==t[i])
++q;
if(q==m) {
mt[++ans] = i - m;
q = pi[m];
}
}
printf("%d\n",ans);
ans = min(ans, 1000); ///PRADUITORILOR!
for(int i=1; i<=ans; ++i)
printf("%d ",mt[i]);
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}