Pagini recente » Cod sursa (job #203857) | Cod sursa (job #1306652) | Cod sursa (job #2854994) | Cod sursa (job #2482372) | Cod sursa (job #1497278)
#include<cstdio>
using namespace std;
const int nMax = 4000000;
char s[nMax];
int Z[nMax], l, sl, af[nMax];
int strlg(char x[]){
int i = 0;
while(x[i] != 0) ++i;
return i;
}
void fZ(){
int L, R, k;
L = R = 0;
for(int i = 0 ; i < l ; ++i){
if(i > R){
L = R = i;
while(s[R] == s[R - L]) ++R;
Z[i] = R - L; --R;
}else{
k = i - L;
if(Z[k] < R - i + 1){
Z[i] = Z[k];
}else{
L = i;
while(s[R] == s[R - L]) ++R;
Z[i] = R - L; --R;
}
}
}
}
int main (){
FILE *in = fopen("strmatch.in","r");
fgets(s, nMax, in);
l = strlg(s);
sl = l;
s[l] = '!';
fgets(s + l + 1, nMax, in);
l = strlg(s);
fclose(in);
fZ();
int sol = 0;
for(int i = 0 ; i < l ; ++i){
if(Z[i] >= sl - 1) af[++sol] = i;
}
FILE *out = fopen("strmatch.out","w");
fprintf(out,"%d\n", sol);
for(int i = 1 ; i <= sol ; ++i)
fprintf(out,"%d ", af[i] - sl - 1);
fprintf(out,"\n");
fclose(out);
return 0;
}