Program KMP Pinggiran C++

Program KMP C++




#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>


using namespace std;


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,F[100];    // 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)
                return i-j; // means, in (i-j)th position, there is a match occur
            else{
                i++;
                j++;
            }
        }else if(j>0){
            j=F[j-1];
        }else{
            i++;
        }
    }
    return -1; // No match found
}




int main(int argc, char *argv[])
{
    //freopen("in.txt","rt",stdin);
    //freopen("out.txt","wt",stdout);
    
cout<<"0:0   1:0   2:0   3:1   4:0   5:0"<<endl;
char T[1000],P[100];
    
    cout<<"teks"<<" = ";
    


while(gets(T)){
cout<<"pola"<<"=";
        gets(P);
        int pos=KMP(T,P);
        if(pos!=-1)
            cout<<"Ditemukan pada index ke- "<<pos<<endl;
        else
            cout<<"tidak ketemu"<<endl;


    }
    system ("color001e");
    system("PAUSE");
    return EXIT_SUCCESS;
}