BasicHashing+UsingMultiplierToAvoidSpuriousHit+UsingModulerToAvoidLargeHashValue

hashing.java

```Java

public class test {

	

	public static void main(String[] args) throws Exception {

		test t = new test();

		// db == cc (100+98) vs (99+99) => 1000  + 980 | 9900 + 990
		// to resolve this we need to multiplier
		t.rabinKarbbHashAvoidSpuriousHitByMulitpler("xxybbcc", "cc");

	}

	public void findSubStringByBasicHash(String text, String pattern) {
		int m = pattern.length();
		int n = text.length();
 		int h = 0;
 		for (int i = 0; i < m; i++) {
			h = h + pattern.charAt(i);
		}

		int c = 0;
		while ( c<n-1){
			int h2 = 0;
			String subt = "";
 			for (int i = c; i < c+m; i++) {
				System.out.println("char "+i+" : "+text.charAt(i)+" "+((int)text.charAt(i)));
				h2 = h2 + text.charAt(i);
				subt = subt + text.charAt(i);
			}
			c++;
			if(h2 == h){
				System.out.println("found pattern start at pointer "+c);
 			}
		}


	}
	public void rabinKarbbHashAvoidSpuriousHitByMulitpler(String text, String pattern) {


		int m = pattern.length();
		int n = text.length();
		int h = 0;
		int d = 10;

		// calc hash
		// init the hash to the value of the high-order digit possition of an m-digit window
		for (int i = 0; i < m; i++) {
			int mmulti = m-i;
			h = h + ((d * mmulti) * pattern.charAt(i) ) ;
		}

 		int c = 0;
		while ( c<n-1){
			int h2 = 0;
			String subt = "";
//			System.out.println("c "+c +" chat  "+ text.charAt(c));
			for (int i = c; i < c+m; i++) {
				int mmulti = m-(i-c);
				System.out.println("char "+i+" : "+text.charAt(i)+" "+((int)text.charAt(i)));
				h2 = h2 + ((d * mmulti) *text.charAt(i)  );
				subt = subt + text.charAt(i);
			}
			c++;
			System.out.println("----"+subt+"-----");

			System.out.println("h2 "+h2);
			System.out.println("h "+h);

			if(h2 == h){
				System.out.println("found pattern start at pointer "+c);
 			}
		}


	}
	public void rabinKarbbHashAvoidSpuriousHitByMulitplerAvoidBigNumberReduceRateOfBigHash(String text, String pattern) {


		int m = pattern.length();
		int n = text.length();
		int h = 0;
		int d = 10;
		int q = 13;

		// calc hash
		// init the hash to the value of the high-order digit possition of an m-digit window
		for (int i = 0; i < m; i++) {
			int mmulti = m-i;
			h = (h + ((d * mmulti) * pattern.charAt(i) )) % q  ;
		}

		int c = 0;
		while ( c<n-1){
			int h2 = 0;
			String subt = "";
//			System.out.println("c "+c +" chat  "+ text.charAt(c));
			for (int i = c; i < c+m; i++) {
				int mmulti = m-(i-c);
				System.out.println("char "+i+" : "+text.charAt(i)+" "+((int)text.charAt(i)));
				h2 = ( h2 + ((d * mmulti) *text.charAt(i)  )) % q ;
				subt = subt + text.charAt(i);
			}
			c++;
			System.out.println("----"+subt+"-----");

			System.out.println("h2 "+h2);
			System.out.println("h "+h);

			if(h2 == h){
				System.out.println("found pattern start at pointer "+c);
			}
		}


	}


	public void findSubStringUsingBasicRollingHashWithoutMulitplieer(String text, String pattern) {


		int m = pattern.length();
		int n = text.length();

		int h = 0;

		for (int i = 0; i < m; i++) {
			h = h + pattern.charAt(i);
		}

		int c = m - 1;
		int h2 = 0;
		for (int i = 0; i < m; i++) {
			h2 = h2 + text.charAt(i);
		}
		while (c < n - 1) {

			if (h2 == h) {
				System.out.println("found pattern start at pointer " + c);

			}

			h2 = (h2 + text.charAt(c + 1)) - text.charAt(c - 1);

			System.out.println("----" + c + "-----");

			System.out.println("h2 " + h2);
			System.out.println("h " + h);

			c++;
			if (h2 == h) {
				System.out.println("found pattern start at pointer " + c);
			}

		}
	}

```