Pagini recente » Cod sursa (job #3190315) | Cod sursa (job #1155206) | Cod sursa (job #640826) | Cod sursa (job #2575207) | Cod sursa (job #670804)
Cod sursa(job #670804)
#include<fstream>
#include<iostream>
#include<cstring>
using namespace std;
#define filein "strmatch.in"
#define fileout "strmatch.out"
FILE *fin, *fout;
char str1[2000002], str2[2000002];
int mInd[1000], current, F[2000002];
void FailureFunction(char P[], int F[],int m){
int i,j;
F[0]=0; // assignment is important!
j=0;
i=1;
while(i<m){ // that i is less than the length of pattern
if(P[i]==P[j]){
F[i]=j+1;
i++;
j++;
}else if(j>0){
j=F[j-1];
}else {
F[i]=0;
i++;
}
}
}
int KMP(char T[], char P[]){
int i,j; // the maximum size of Pattern String
int m=strlen(P);
int n=strlen(T);
FailureFunction(P,F,m);
i=0;
j=0;
while(i<n){
if(T[i]==P[j]){
if(j==m-1){
mInd[current] = i-j;
current++;
j++;
}
else{
i++;
j++;
}
}else if(j>0){
j=F[j-1];
}else{
i++;
}
}
return -1; // No match found
}
int main()
{
fin = fopen(filein, "r");
fgets(str1, 2000001, fin);
fgets(str2, 2000001, fin);
str1[strlen(str1) - 1] = '\0';
fclose(fin);
current = 0;
KMP(str2, str1);
fout = fopen(fileout, "w");
fprintf(fout, "%d\n", current);
for(int i = 0; i < current; i++)
fprintf(fout, "%d ", mInd[i]);
fclose(fout);
return 0;
}