Pagini recente » Cod sursa (job #2344091) | Cod sursa (job #2636134) | Cod sursa (job #2630459) | Cod sursa (job #1570078) | Cod sursa (job #355903)
Cod sursa(job #355903)
#include <stdio.h>
#include <string.h>
#define DIM 2000002
char A[DIM];
char B[DIM];
int P[DIM];
int S[1002];
int dA, dB, i, k, sol;
int main(){
FILE *f = fopen("strmatch.in","r");
fscanf(f,"%s",A);
fscanf(f,"%s",B);
fclose(f);
for (i = dA = strlen(A); i>0; i--)
A[i] = A[i-1];
for (i = dB = strlen(B); i>0; i--)
B[i] = B[i-1];
//fac prefix pentru A (subsirul)
//P[i] = cel mai lung prefix care este si dufix ce se termina pe pozitia i
P[1] = 0;
for (i=2, k=0;i<=dA;i++) {
while (A[i] != A[k+1] && k>0)
k = P[k];
if (A[i] == A[k+1]) {
k++;
P[i] = k;
}/* else
P[i] = 0;*/
}
for (i=1,k=0;i<=dB;i++) {
while (k && B[i]!=A[k+1])
k = P[k];
if (B[i] == A[k+1]) {
k++;
if (k == dA) {
sol++;
if (sol <= 1000)
S[sol] = i-dA;
}
}
}
FILE *g = fopen("strmatch.out","w");
fprintf(g,"%d\n",sol);
if (sol>1000)
sol = 1000;
for (i = 1;i<=sol;i++)
fprintf(g,"%d ",S[i]);
fclose(g);
return 0;
}