Pagini recente » Cod sursa (job #1803637) | Cod sursa (job #1297342) | Cod sursa (job #267249) | Cod sursa (job #554001) | Cod sursa (job #955110)
Cod sursa(job #955110)
#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");
do { fscanf(f, "%c", pattern+n); } while(pattern[n++]!='\n');
do { fscanf(f, "%c", text+m); m++; }while(!feof(f));
n--; m-=2;
//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;
}