forked from jainaman224/Algo_Ds_Notes
-
Notifications
You must be signed in to change notification settings - Fork 0
/
KMP.kt
83 lines (72 loc) · 1.92 KB
/
KMP.kt
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
81
82
83
/*
Knuth Morris Pratt String Searching Algorithm
Given a text txt[0..n-1] and a pattern pat[0..m-1], the algo will find all occurrences of pat[] in txt[]
*/
import java.util.*
internal class KMP {
fun kmpSearch(pat: String, txt: String) {
val m = pat.length
val n = txt.length
// longest_prefix_suffix array
val lps = IntArray(m)
// index for pat[]
var j = 0
//calculate lps[] array
computeLPSArray(pat, m, lps)
//index for txt[]
var i = 0
while (i < n) {
if (pat[j] == txt[i]) {
j++
i++
}
if (j == m) {
println("Found pattern at index" + (i - j))
j = lps[j - 1]
} else if (i < n && pat[j] != txt[i]) {
if (j != 0) j = lps[j - 1] else i += 1
}
}
}
// length of the previous longest prefix suffix
private fun computeLPSArray(pat: String, M: Int, lps: IntArray) {
var len = 0
var i = 1
//lps[0] is always 0
lps[0] = 0
//calculate lps[i] for i=1 to M-1
while (i < M)
{
if (pat[i] == pat[len]) {
len++
lps[i] = len
i++
}
else {
if (len != 0) len = lps[len - 1] else {
lps[i] = len
i++
}
}
}
}
companion object {
//Driver program to test above function
@JvmStatic
fun main(args: Array<String>) {
val sc = Scanner(System.`in`)
val txt = sc.nextLine()
val pat = sc.nextLine()
KMP().kmpSearch(pat, txt)
}
}
}
/*
Sample Input
namanchamanbomanamansanam
aman
Sample Output:
Patterns occur at shift = 1
Patterns occur at shift = 7
Patterns occur at shift = 16
*/