-
Notifications
You must be signed in to change notification settings - Fork 0
/
comLPS.cpp
78 lines (64 loc) · 1.16 KB
/
comLPS.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <string.h>
using namespace std;
void clps (char ptn[] , int n , int LPS[]);
void kmpSearch (char ptn[] , char txt[] ,int n , int m);
void printArr(int arr[] , int s){
for (int i=0; i<s ; i++){
cout<<' '<<arr[i];
}
cout<<endl;
}
int main(int argc, char *argv[])
{
char ptn [8]={'A','A','B','A','A','A','B','A'};
//AABAAABA
char txt[17] ={'A','B','A','B','A','B','C','A','B','A','B','A','B','A','C','B','C'};
kmpSearch (ptn , txt , 17,8);
return 0;
}
void clps (char ptn[] , int n , int LPS[]){
int i=1 , j=0;
LPS[0]=0;
while(i<n){
if (ptn[i] == ptn[j]){
j++;
LPS[i] = j;
i++;
}
else{
if (j!=0){
j = LPS[j-1];
}
else{
LPS[i] = 0;
i++;
}
}
}
}
void kmpSearch (char ptn[] , char txt[] , int n , int m){
int lps[m];
clps (ptn , m , lps);
cout<<"LPS = "; printArr(lps , m);
int i=0 , j=0;
while (i<n){
//cout<<"i = "<<i << " , j= "<<j <<endl;
if (ptn[i] == txt[j]){
j++;
i++;
}
if (j==m){
cout<<"founded at pos = "<<i-j<<endl;
j=lps[j-1];
}
else if ((i<n) && (ptn[i]!=txt[j])){
if (j!=0){
j = lps[j-1];
}
else{
i++;
}
}
}
}