CodeJava/KMP.java at master · sidhant55/CodeJava · GitHub

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
package Data_Structure;

import java.util.*;

public class KMP {
    void Search(String patern, String text)
    {
        int l1=patern.length();
        int l2=text.length();

        int lps[]=new int [l1];

        createLPS(patern, l1,lps);
        int i;
        for ( i=0;i<l1;i++)
        System.out.print(lps[i]+" ");
        System.out.println();
        i=0;
        int j=0;
        while(i<l2)
        {
            if (patern.charAt(j)==text.charAt(i))
            {
                j++;
                i++;
            }
            if (j==l1)
            {
                System.out.print("Found "+(i-j));
                j=lps[j-1];
            }
            else if (i<l2 && patern.charAt(j)!=text.charAt(i))
            {
                if (j!=0)
                    j=lps[j-1];
                else
                    i=i+1;
            }
        }
    }

    void createLPS(String patern, int l, int lps[])
    {
        int len=0;
        int i=1;
        lps[0]=0;

        while (i<l)
        {
            if (patern.charAt(i)==patern.charAt(len))
            {
                len++;
                lps[i]=len;
                i++;
            }
            else
            {
                if (len!=0)
                    len=lps[len-1];
                else
                {
                    lps[i]=len;
                    i++;
                }
            }

        }
    }
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        String txt = "ABACABABA";
        String pat = "ABA";
        new KMP().Search(pat,txt);
    }
}