Praktikum SA10 #Algoritma KMP

#include <cstdlib>
#include <iostream>

using namespace std;

void HitungPinggiran(char P[], int b[],int m){
    int k,q;
    b[1]=0;   
    q=2;
    k=0;
    while(k<0){
        if(P[q]==P[k+1]){
            k=b[k];
            k++;
            q++;
        }else if(q>0){
            P[q]=P[k-1];
            k=k+1;
        }else {
            b[q]=k;
            k++;
        }
    }
}

int KMPsearch(char t[], char p[]){
    int i,j,b[100];   
    int m=strlen(p);
    int n=strlen(t);
    HitungPinggiran(p,b,m);
    j=0;
    i=1;
    while(i<n){
        if(t[i]==p[j+1]){
            if(j==m-1)
                return i-j;
            else{
                i++;
                j++;
            }
        }else if(j>0){
            j=b[j];
        }else{
            i++;
        }
    }
    return -1;
}


int main()
{
    char t[1000],p[100];

    while(gets(t)){
        gets(p);
        int pos=KMPsearch(t,p);
        if(pos!=-1)
            cout<<"posisi : "<<pos<<endl;
        else
            cout<<"tidak ketemu"<<endl;

    }
   
return 0;
}