forked from thuva4/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRabinKarp.java
More file actions
60 lines (56 loc) · 1.6 KB
/
RabinKarp.java
File metadata and controls
60 lines (56 loc) · 1.6 KB
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
/*
* Author:- Prarik Kayastha
* Email-id:- [email protected]
* Program Name:- Rabin-Karp Algorithm
* Description:- This algorithm uses to find pattern in given string.
* Time-Complexity:- O(mn)
* */
import java.util.Scanner;
public class RabinKarp {
static final long prime = 101;
public static String searchSubstring(String str,int n,String sub,int m)
{
long key= getSubKey(sub, m);
long oldHash = getSubKey(str.substring(0, m), m);
if(key==oldHash && equal(str, sub, 0))
return "Yes";
for(int i=m;i<n;i++)
{
oldHash = getNewHash(str, i-m, i, oldHash, m);
if(key==oldHash && equal(str, sub, i-m+1))
return "Yes";
}
return "No";
}
public static long getNewHash(String str,int oldIndex,int newIndex,long oldHash,int m)//get newhash in constant time
{
long newHash=((oldHash-str.charAt(oldIndex)+96)/prime)+((str.charAt(newIndex)-96)*(long)Math.pow(prime, m-1));
return newHash;
}
public static long getSubKey(String sub,int m)//hashing function
{
long key=0;
for(int i=0;i<m;i++)
{
key += (sub.charAt(i)-96)*(long)Math.pow(prime, i);
}
return key;
}
public static boolean equal(String str,String sub,int index)//to check two string are equal or not
{
for(int i=0;i<sub.length();i++)
if(str.charAt(index+i)!=sub.charAt(i))
return false;
return true;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
String sub = sc.nextLine();
int n = str.length();
int m = sub.length();
System.out.println(searchSubstring(str,n,sub,m));
sc.close();
}
}