Pagini recente » Profil atpkekw | Cod sursa (job #1069080) | Cod sursa (job #1881292) | Istoria paginii runda/w1 | 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;
}