Pagini recente » Rating zaharia (zaha1234) | Cod sursa (job #1105313) | Cod sursa (job #498249) | Cod sursa (job #472615) | Cod sursa (job #1979125)
#include <cstdio>
#include <ctype.h>
const int MAX_N = 2000000;
const int BUFF = 4096;
char sir[MAX_N+1+MAX_N];
int curs = BUFF - 1;
int d[MAX_N+1+MAX_N];
char buff[BUFF];
char nextch(FILE *fin) {
++curs;
if(curs == BUFF) {
curs = 0;
fread(buff, 1, BUFF, fin);
}
return buff[curs];
}
char getch(FILE *fin) {
char ch = nextch(fin);
while(ch == ' ')
ch = nextch(fin);
return ch;
}
int rez[1000];
int main() {
int n1, n2, st, dr, top = 0, n3;
FILE *fin = fopen("strmatch.in", "r");
n1 = n2 = 0;
char ch = getch(fin);
while(isalpha(ch) || isdigit(ch)) {
sir[n1++] = ch;
ch = getch(fin);
}
ch = getch(fin);
while(isalpha(ch) || isdigit(ch)) {
++n2;
sir[n1+n2] = ch;
ch = getch(fin);
}
fclose(fin);
n3 = n1 + 1 + n2;
d[0] = 1;
st = dr = 0;
for(int i = 1; i < n3; ++i) {
if(i > dr) {
d[i] = 0;
while(i + d[i] < n3 && sir[d[i]] == sir[i+d[i]]) {
++d[i];
++dr;
}
st = i;
}
if(i < dr) {
d[i] = d[i - st];
if(i + d[i] >= dr) {
d[i] = dr - i + 1;
st = i;
while(i + d[i] < n3 && sir[d[i]] == sir[i+d[i]]) {
++d[i];
++dr;
}
}
}
if(d[i] == n1) {
if(top < 1000)
rez[top] = i - n1 - 1;
++top;
}
}
FILE *fout = fopen("strmatch.out", "w");
fprintf(fout, "%d\n", top);
for(int i = 0; i < top && i < 1000; ++i)
fprintf(fout, "%d ", rez[i]);
fclose(fout);
return 0;
}