Pagini recente » Cod sursa (job #779858) | Cod sursa (job #395368) | Cod sursa (job #855149) | Cod sursa (job #774176) | Cod sursa (job #955082)
Cod sursa(job #955082)
#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;
FILE *f = fopen("strmatch.in", "r");
FILE *g = fopen("strmatch.out", "w");
fgets(pattern, sizeof(pattern), f); while((pattern[n]>='A' && pattern[n]<='Z') || (pattern[n]>='a' && pattern[n]<='z') || (pattern[n]>='0' && pattern[n]<='9')) n++;
fgets(text, sizeof(text), f); while((text[m]>='A' && text[m]<='Z') || (text[m]>='a' && text[m]<='z') ||(text[m]>='0' && text[m]<='9')) m++;
//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];
}
}
fprintf(g, "%d\n", pn);
for(i=0; i<pn; i++)
fprintf(g, "%d ", result[i]);
return 0;
}