algorithms/Java/KmpAlgorithm.java at master · AASF-IIITM/algorithms · 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
classKMP_String_Matching {
voidKMPSearch(Stringpat, Stringtxt)
	{
intM = pat.length();
intN = txt.length();


intlps[] = newint[M];
intj = 0; // index for pat[]


computeLPSArray(pat, M, lps);

inti = 0; // index for txt[]
while (i < N) {
if (pat.charAt(j) == txt.charAt(i)) {
j++;
i++;
 }
if (j == M) {
System.out.println("Found pattern "
 + "at index " + (i - j));
j = lps[j - 1];
 }

elseif (i < N && pat.charAt(j) != txt.charAt(i)) {

if (j != 0)
j = lps[j - 1];
else
i = i + 1;
 }
 }
	}

voidcomputeLPSArray(Stringpat, intM, intlps[])
	{

intlen = 0;
inti = 1;
lps[0] = 0; // lps[0] is always 0


while (i < M) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
 }
else
 {

if (len != 0) {
len = lps[len - 1];


 }
else// if (len == 0)
 {
lps[i] = len;
i++;
 }
 }
 }
	}


publicstaticvoidmain(Stringargs[])
	{
Stringtxt = "ABABDABACDABABCABAB";
Stringpat = "ABABCABAB";
newKMP_String_Matching().KMPSearch(pat, txt);
	}
}
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
classKMP_String_Matching {
voidKMPSearch(Stringpat, Stringtxt)
	{
intM = pat.length();
intN = txt.length();


intlps[] = newint[M];
intj = 0; // index for pat[]


computeLPSArray(pat, M, lps);

inti = 0; // index for txt[]
while (i < N) {
if (pat.charAt(j) == txt.charAt(i)) {
j++;
i++;
 }
if (j == M) {
System.out.println("Found pattern "
 + "at index " + (i - j));
j = lps[j - 1];
 }

elseif (i < N && pat.charAt(j) != txt.charAt(i)) {

if (j != 0)
j = lps[j - 1];
else
i = i + 1;
 }
 }
	}

voidcomputeLPSArray(Stringpat, intM, intlps[])
	{

intlen = 0;
inti = 1;
lps[0] = 0; // lps[0] is always 0


while (i < M) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
 }
else
 {

if (len != 0) {
len = lps[len - 1];


 }
else// if (len == 0)
 {
lps[i] = len;
i++;
 }
 }
 }
	}


publicstaticvoidmain(Stringargs[])
	{
Stringtxt = "ABABDABACDABABCABAB";
Stringpat = "ABABCABAB";
newKMP_String_Matching().KMPSearch(pat, txt);
	}
}
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
classKMP_String_Matching {
voidKMPSearch(Stringpat, Stringtxt)
	{
intM = pat.length();
intN = txt.length();


intlps[] = newint[M];
intj = 0; // index for pat[]


computeLPSArray(pat, M, lps);

inti = 0; // index for txt[]
while (i < N) {
if (pat.charAt(j) == txt.charAt(i)) {
j++;
i++;
 }
if (j == M) {
System.out.println("Found pattern "
 + "at index " + (i - j));
j = lps[j - 1];
 }

elseif (i < N && pat.charAt(j) != txt.charAt(i)) {

if (j != 0)
j = lps[j - 1];
else
i = i + 1;
 }
 }
	}

voidcomputeLPSArray(Stringpat, intM, intlps[])
	{

intlen = 0;
inti = 1;
lps[0] = 0; // lps[0] is always 0


while (i < M) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
 }
else
 {

if (len != 0) {
len = lps[len - 1];


 }
else// if (len == 0)
 {
lps[i] = len;
i++;
 }
 }
 }
	}


publicstaticvoidmain(Stringargs[])
	{
Stringtxt = "ABABDABACDABABCABAB";
Stringpat = "ABABCABAB";
newKMP_String_Matching().KMPSearch(pat, txt);
	}
}
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
classKMP_String_Matching {
voidKMPSearch(Stringpat, Stringtxt)
	{
intM = pat.length();
intN = txt.length();


intlps[] = newint[M];
intj = 0; // index for pat[]


computeLPSArray(pat, M, lps);

inti = 0; // index for txt[]
while (i < N) {
if (pat.charAt(j) == txt.charAt(i)) {
j++;
i++;
 }
if (j == M) {
System.out.println("Found pattern "
 + "at index " + (i - j));
j = lps[j - 1];
 }

elseif (i < N && pat.charAt(j) != txt.charAt(i)) {

if (j != 0)
j = lps[j - 1];
else
i = i + 1;
 }
 }
	}

voidcomputeLPSArray(Stringpat, intM, intlps[])
	{

intlen = 0;
inti = 1;
lps[0] = 0; // lps[0] is always 0


while (i < M) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
 }
else
 {

if (len != 0) {
len = lps[len - 1];


 }
else// if (len == 0)
 {
lps[i] = len;
i++;
 }
 }
 }
	}


publicstaticvoidmain(Stringargs[])
	{
Stringtxt = "ABABDABACDABABCABAB";
Stringpat = "ABABCABAB";
newKMP_String_Matching().KMPSearch(pat, txt);
	}
}
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
classKMP_String_Matching {
voidKMPSearch(Stringpat, Stringtxt)
	{
intM = pat.length();
intN = txt.length();


intlps[] = newint[M];
intj = 0; // index for pat[]


computeLPSArray(pat, M, lps);

inti = 0; // index for txt[]
while (i < N) {
if (pat.charAt(j) == txt.charAt(i)) {
j++;
i++;
 }
if (j == M) {
System.out.println("Found pattern "
 + "at index " + (i - j));
j = lps[j - 1];
 }

elseif (i < N && pat.charAt(j) != txt.charAt(i)) {

if (j != 0)
j = lps[j - 1];
else
i = i + 1;
 }
 }
	}

voidcomputeLPSArray(Stringpat, intM, intlps[])
	{

intlen = 0;
inti = 1;
lps[0] = 0; // lps[0] is always 0


while (i < M) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
 }
else
 {

if (len != 0) {
len = lps[len - 1];


 }
else// if (len == 0)
 {
lps[i] = len;
i++;
 }
 }
 }
	}


publicstaticvoidmain(Stringargs[])
	{
Stringtxt = "ABABDABACDABABCABAB";
Stringpat = "ABABCABAB";
newKMP_String_Matching().KMPSearch(pat, txt);
	}
}
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
classKMP_String_Matching {
voidKMPSearch(Stringpat, Stringtxt)
	{
intM = pat.length();
intN = txt.length();


intlps[] = newint[M];
intj = 0; // index for pat[]


computeLPSArray(pat, M, lps);

inti = 0; // index for txt[]
while (i < N) {
if (pat.charAt(j) == txt.charAt(i)) {
j++;
i++;
 }
if (j == M) {
System.out.println("Found pattern "
 + "at index " + (i - j));
j = lps[j - 1];
 }

elseif (i < N && pat.charAt(j) != txt.charAt(i)) {

if (j != 0)
j = lps[j - 1];
else
i = i + 1;
 }
 }
	}

voidcomputeLPSArray(Stringpat, intM, intlps[])
	{

intlen = 0;
inti = 1;
lps[0] = 0; // lps[0] is always 0


while (i < M) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
 }
else
 {

if (len != 0) {
len = lps[len - 1];


 }
else// if (len == 0)
 {
lps[i] = len;
i++;
 }
 }
 }
	}


publicstaticvoidmain(Stringargs[])
	{
Stringtxt = "ABABDABACDABABCABAB";
Stringpat = "ABABCABAB";
newKMP_String_Matching().KMPSearch(pat, txt);
	}
}
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
classKMP_String_Matching {
voidKMPSearch(Stringpat, Stringtxt)
	{
intM = pat.length();
intN = txt.length();


intlps[] = newint[M];
intj = 0; // index for pat[]


computeLPSArray(pat, M, lps);

inti = 0; // index for txt[]
while (i < N) {
if (pat.charAt(j) == txt.charAt(i)) {
j++;
i++;
 }
if (j == M) {
System.out.println("Found pattern "
 + "at index " + (i - j));
j = lps[j - 1];
 }

elseif (i < N && pat.charAt(j) != txt.charAt(i)) {

if (j != 0)
j = lps[j - 1];
else
i = i + 1;
 }
 }
	}

voidcomputeLPSArray(Stringpat, intM, intlps[])
	{

intlen = 0;
inti = 1;
lps[0] = 0; // lps[0] is always 0


while (i < M) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
 }
else
 {

if (len != 0) {
len = lps[len - 1];


 }
else// if (len == 0)
 {
lps[i] = len;
i++;
 }
 }
 }
	}


publicstaticvoidmain(Stringargs[])
	{
Stringtxt = "ABABDABACDABABCABAB";
Stringpat = "ABABCABAB";
newKMP_String_Matching().KMPSearch(pat, txt);
	}
}
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
classKMP_String_Matching {
voidKMPSearch(Stringpat, Stringtxt)
	{
intM = pat.length();
intN = txt.length();


intlps[] = newint[M];
intj = 0; // index for pat[]


computeLPSArray(pat, M, lps);

inti = 0; // index for txt[]
while (i < N) {
if (pat.charAt(j) == txt.charAt(i)) {
j++;
i++;
 }
if (j == M) {
System.out.println("Found pattern "
 + "at index " + (i - j));
j = lps[j - 1];
 }

elseif (i < N && pat.charAt(j) != txt.charAt(i)) {

if (j != 0)
j = lps[j - 1];
else
i = i + 1;
 }
 }
	}

voidcomputeLPSArray(Stringpat, intM, intlps[])
	{

intlen = 0;
inti = 1;
lps[0] = 0; // lps[0] is always 0


while (i < M) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
 }
else
 {

if (len != 0) {
len = lps[len - 1];


 }
else// if (len == 0)
 {
lps[i] = len;
i++;
 }
 }
 }
	}


publicstaticvoidmain(Stringargs[])
	{
Stringtxt = "ABABDABACDABABCABAB";
Stringpat = "ABABCABAB";
newKMP_String_Matching().KMPSearch(pat, txt);
	}
}