Cod sursa(job #670804)

Utilizator impulseBagu Alexandru impulse Data 30 ianuarie 2012 10:31:29
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#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;
}