Thursday, 7 June 2012
Program KMP :
#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<<endl;
else
cout<<"\ntidak ketemu"<<endl<<endl;
//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<<endl;
else
cout<<"\ntidak ketemu"<<endl; }
system ("color001e");
system("PAUSE");
return EXIT_SUCCESS;}}
Posted on 19:08 by yusufruli
Subscribe to:
Post Comments (Atom)
Popular Posts
-
Nemu artikel bagus nih tentang agama. Gak ada salahnya saya posting, apalagi sebelum bulan ramadhan ini. TAKHALLI sesungguhnya berunt...
-
#include <cstdlib> #include <iostream> using namespace std; int floor(double x){ int a; ...
-
KATA PENGANTAR
Blog Archive
-
▼
2012
(49)
-
▼
Jun
(19)
- Apakah Software JAVA = Nama Pulau Di Indonesia?
- 8 Bocoran "Orang Dalam" untuk Tiket Pesawat Murah
- FILOSOFI ANGKA 7
- Mau Uang Jutaan Rupiah? Ikuti Kontes Status FB Ini
- Postest Grafika Komputer 1 sampai 10
- Cara Partisi Hardisk Eksternal
- Program Knapsack Fractional C++
- Praktikum Sistem Informasi 1 sampai 10
- program prims
- Program Dijkstra (Lintasan Terependek)
- Program Pembulatan c++
- Program MERGE SORT c++
- Program BUBBLE SORT c++
- Hal Yang Membedakan Indonesia Dengan Jepang
- Sepuluh Internet Browser Terbaik 2012
- Program KMP String Matching
- Partition Sort c++
- Program Sorting Gabungan
- Program Pencarian Data
-
▼
Jun
(19)
|
[close]
Powered by Blogger.
0 komentar:
Post a Comment