FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/Others/RabinKarp.java at dev · primary-code-test/Java · GitHub
primary-code-test
Java
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java
/
Others
/
RabinKarp.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
79 lines (63 loc) · 2.51 KB
Breadcrumbs
Java
/
Others
/
RabinKarp.java
Copy path
File metadata and controls
79 lines (63 loc) · 2.51 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
/** @author Prateek Kumar Oraon (https://github.com/prateekKrOraon) */
import
java
.
util
.
Scanner
;
// An implementation of Rabin-Karp string matching algorithm
// Program will simply end if there is no match
public
class
RabinKarp
{
public
static
Scanner
scanner
=
null
;
public
static
final
int
d
=
256
;
public
static
void
main
(
String
[]
args
) {
scanner
=
new
Scanner
(
System
.
in
);
System
.
out
.
println
(
"Enter String"
);
String
text
=
scanner
.
nextLine
();
System
.
out
.
println
(
"Enter pattern"
);
String
pattern
=
scanner
.
nextLine
();
int
q
=
101
;
searchPat
(
text
,
pattern
,
q
);
}
private
static
void
searchPat
(
String
text
,
String
pattern
,
int
q
) {
int
m
=
pattern
.
length
();
int
n
=
text
.
length
();
int
t
=
0
;
int
p
=
0
;
int
h
=
1
;
int
j
=
0
;
int
i
=
0
;
h
= (
int
)
Math
.
pow
(
d
,
m
-
1
) %
q
;
for
(
i
=
0
;
i
<
m
;
i
++) {
// hash value is calculated for each character and then added with the hash value of the next
// character for pattern
// as well as the text for length equal to the length of pattern
p
= (
d
*
p
+
pattern
.
charAt
(
i
)) %
q
;
t
= (
d
*
t
+
text
.
charAt
(
i
)) %
q
;
}
for
(
i
=
0
;
i
<=
n
-
m
;
i
++) {
// if the calculated hash value of the pattern and text matches then
// all the characters of the pattern is matched with the text of length equal to length of the
// pattern
// if all matches then pattern exist in string
// if not then the hash value of the first character of the text is subtracted and hash value
// of the next character after the end
// of the evaluated characters is added
if
(
p
==
t
) {
// if hash value matches then the individual characters are matched
for
(
j
=
0
;
j
<
m
;
j
++) {
// if not matched then break out of the loop
if
(
text
.
charAt
(
i
+
j
) !=
pattern
.
charAt
(
j
))
break
;
}
// if all characters are matched then pattern exist in the string
if
(
j
==
m
) {
System
.
out
.
println
(
"Pattern found at index "
+
i
);
}
}
// if i<n-m then hash value of the first character of the text is subtracted and hash value of
// the next character after the end
// of the evaluated characters is added to get the hash value of the next window of characters
// in the text
if
(
i
<
n
-
m
) {
t
= (
d
* (
t
-
text
.
charAt
(
i
) *
h
) +
text
.
charAt
(
i
+
m
)) %
q
;
// if hash value becomes less than zero than q is added to make it positive
if
(
t
<
0
)
t
= (
t
+
q
);
}
}
}
}
Back
|
FazBrowse Home
|
New Git URL