FilesExpand file tree

 master

/

KmpPatternMatching.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

80 lines (76 loc) · 2.36 KB

 master

/

KmpPatternMatching.java

Copy path

Top

File metadata and controls

• Code
• Blame

80 lines (76 loc) · 2.36 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

79

80

package kmp.pattern.matching;

class KMP_string_matching{

public void KMPserach(String pattern,String text){

int m=pattern.length();

int n=text.length();

// create lps[] that will hold the longest

// prefix suffix values for pattern

int[] lps=new int[m];

// index for pat[]

int j=0;

// Preprocess the pattern (calculate lps[]

// array)

computeLpsArray(pattern,m,lps);

int i=0;

while(i<n){

if(pattern.charAt(j)==text.charAt(i)){

j++;

i++;

}

if(j==m){

System.out.println("Found pattern at index : "+(i-j));

j=lps[j-1];

}

// mismatch after j matches

else if(i<n && pattern.charAt(j)!=text.charAt(i)){

// Do not match lps[0..lps[j-1]] characters,

// they will match anyway

if(j!=0){

j=lps[j-1];

}

else{

i++;

}

}

}

}

public void computeLpsArray(String pattern,int m,int[] lps){

// length of the previous longest prefix suffix

int len=0;

int i=1;

// lps[0] is always 0

lps[0]=0;

// the loop calculates lps[i] for i = 1 to M-1

while(i<m){

if(pattern.charAt(i)==pattern.charAt(len)){

len++;

lps[i]=len;

i++;

}

// (pat[i] != pat[len])

else{

// This is tricky. Consider the example.

// AAACAAAA and i = 7. The idea is similar

// to search step.

if(len!=0){

len=lps[len-1];

// Also, note that we do not increment

// i here

}

// if (len == 0)

else{

lps[i]=len;

i++;

}

}

}

}

}

public class KmpPatternMatching {

public static void main(String[] args) {

KMP_string_matching kmp=new KMP_string_matching();

String text="AAAABAAAA";

String pattern="AAAA";

kmp.KMPserach(pattern, text);

}

}