Pagini recente » Cod sursa (job #371626) | Cod sursa (job #2415410) | Cod sursa (job #1449457) | Cod sursa (job #593794) | Cod sursa (job #152998)
Cod sursa(job #152998)
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define lg 2000001
char s1[lg], s2[lg], sr1[lg], sr2[lg];
int x1, x2, i, x, urm[lg], nr[1001], nrs;
void prefix(){
int i, k = 0;
for (i = 2; i <= x1; i ++){
while (k > 0 && sr1[k+1] != sr1[i])
k = urm[k];
if (sr1[k+1] == sr1[i])
k ++;
urm[i] = k;
}
}
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s%s", s1, s2);
x1 = strlen(s1);
x2 = strlen(s2);
for (i = 0; i < x1; i ++)
sr1[i+1] = s1[i];
for (i = 0; i < x2; i ++)
sr2[i+1] = s2[i];
prefix();
for (i = 1; i <= x2; i ++){
while (x > 0 && sr1[x+1] != sr2[i])
x = urm[x];
if (sr1[x+1] == sr2[i])
x ++;
if (x == x1){
nrs ++;
if (nrs <= 1000)
nr[nrs] = i-x1;
}
}
printf("%d\n", nrs);
for (i = 1; i <= min(nrs, 1000); i ++)
printf("%d ", nr[i]);
printf("\n");
return 0;
}