Pagini recente » Cod sursa (job #2876567) | Borderou de evaluare (job #1515248) | Cod sursa (job #2805880) | Cod sursa (job #955049) | Cod sursa (job #955098)
Cod sursa(job #955098)
#include<stdio.h>
#include<string.h>
#define NMax 2000001
char pattern[NMax], text[NMax], d;
int pi[NMax], pn = 0, result[1024];
int n,m;
int main(){
int i, k=0;
FILE *f = fopen("strmatch.in", "r");
FILE *g = fopen("strmatch.out", "w");
fgets(pattern, sizeof(pattern), f); n= strlen(pattern);
fgets(text, sizeof(text), f); m=strlen(text);
//CREATE PI
pi[0] = 0;
for(i=1; i<n; i++){
while(k>0 && pattern[i]!=pattern[k])
k=pi[k];
if(pattern[i]==pattern[k])
k++;
pi[i] = k;
}
//FIND RESULTS
k=0;
for(i=0; i<m; i++){
while(k>0 && text[i]!=pattern[k])
k=pi[k-1];
if(text[i] == pattern[k])
k++;
if(k==n){
if(pn<1000)
result[pn] = i-n+1;
k=pi[k-1];
pn++;
}
}
fprintf(g, "%d\n", pn);
if(pn>1000) pn =1000;
for(i=0; i<pn; i++)
fprintf(g, "%d ", result[i]);
return 0;
}