fork download 
  1. /**
  2.  * Rabin Karp uses hashing technique to search for Strings 
  3.  * @author PRATEEK Rathore
  4.  */
  5. class RabinKarp {
  6.  
  7. 	//Contant prime number
  8. 	private static final int CONSTANT_PRIME = 101;
  9. 	//Hash Value of the pattern which will remain constant through out the problem
  10. 	private long pathash;
  11. 	private int radix;
  12. 	//Input pattern
  13. 	private String pat;
  14. 	//Pattern Length
  15. 	private int patLen;
  16.  
  17. 	//Its the place value of Most Significant bit
  18. 	private long RM1;
  19.  
  20. 	//Preprocessing of pattern in the constructor
  21. 	public RabinKarp( String pat) {
  22. 		radix = 256;
  23. 		patLen = pat.length();
  24. 		this.pat = pat;
  25.  
  26. 		RM1 = 1;
  27. 		for (int i = 1; i < patLen; i++)
  28. 			RM1 = (radix * RM1) % CONSTANT_PRIME;
  29.  
  30. 		//return hash value of pattern
  31. 		pathash = hash(pat, patLen);
  32. 	}
  33.  
  34. 	//Return hash value of given string from 0 to the input length
  35. 	private long hash(String pat, int len) {
  36. 		long h = 0;
  37. 		for (int j = 0; j < len; j++)
  38. 			h = (radix * h + pat.charAt(j)) % CONSTANT_PRIME;
  39. 		return h;
  40. 	}
  41.  
  42. 	/**
  43. 	 * Sub-routine called when hash-function is equal,
  44. 	 * character by character comparison is done.
  45. 	 */
  46. 	private boolean doesMatch(String text, int currIndex) {
  47. 		for (int j = 0; j < patLen; j++)
  48. 			if (pat.charAt(j) != text.charAt(currIndex + 1 + j))
  49. 				return false;
  50. 		return true;
  51. 	}
  52.  
  53. 	/**
  54. 	 * Search for the pattern in the input string
  55. 	 * @param text
  56. 	 * @return: index where pattern is found in text
  57. 	 */
  58. 	public int search(String text) {
  59. 		int textLen = text.length();
  60. 		if (patLen > textLen)
  61. 			return -1;
  62.  
  63. 		long textHash = hash(text, patLen);
  64.  
  65. 		for (int i = 0; i < textLen - patLen; i++) {
  66. 			textHash = radix * (textHash - RM1 * text.charAt(i))% CONSTANT_PRIME   +   
  67. 							CONSTANT_PRIME + text.charAt(i + patLen) % CONSTANT_PRIME;
  68. 			if (textHash == pathash && doesMatch(text, i))
  69. 				return i;
  70. 		}
  71. 		return -1;
  72. 	}
  73.  
  74. 	public static void main(String[] args) {
  75.  
  76. 		String pat = "prateek";
  77. 		String txt = "Welcome prateek to Bangalore";
  78.  
  79. 		RabinKarp rabin = new RabinKarp( pat);
  80. 		int index= rabin.search(txt);
  81. 		System.out.println("Text found at "+ index + ": " + txt.substring(index, index+ pat.length()+1));
  82. 	}
  83. }
  84.  
Success #stdin #stdout 0.06s 380224KB
comments (?)
stdin 
Standard input is empty
stdout 
Text found at 7:  prateek
https://ideone.com/Ssj1OF
Rabin Karp
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!