Pagini recente » Cod sursa (job #955979) | Cod sursa (job #529544) | Cod sursa (job #1837651) | Cod sursa (job #2143790) | Cod sursa (job #2487254)
#include<cstdio>
#include<cstring>
const int RMAX = 1000;
const int LMAX = 2000000;
char P[1 + LMAX + 1];
char T[LMAX + 1];
int v[RMAX + 1];
int lps[LMAX + 1];
int main()
{
freopen("strmatch.in" , "r" , stdin);
freopen("strmatch.out" , "w" , stdout);
scanf("%s" , P + 1);
scanf("%s" , T);
int n = strlen(P + 1);
int m = strlen(T);
lps[0] = 0;
lps[1] = 0;
for (int i = 2; i <= n; i++) {
int x = lps[i - 1];
while (x > 0 && P[x + 1] != P[i]) {
x = lps[x];
}
if (P[x + 1] == P[i]) {
lps[i] = x + 1;
} else {
lps[i] = 0;
}
}
int x = 0 , contor = 0 ;
for (int i = 0; i < m; i++) {
while (x > 0 && P[x + 1] != T[i]) {
x = lps[x];
}
if (P[x + 1] == T[i]) {
x++;
} else {
x = 0;
}
if (x == n) {
contor ++;
v[contor] = i;
}
}
printf("%d\n" , contor);
if(contor > 1000)
contor = 1000;
for(int i = 1; i <= contor ; i ++)
{
printf("%d " , v[i] - n + 1);
}
return 0;
}