package com.company;

import java.math.BigInteger;

public class Main {

    public static void main(String[] args) {
        String text = "some some Text toto find to in smths";
        String pattern = "to";
        System.out.println(hash(pattern));
        rabinCarp(text, pattern);
    }

    public static int hash(String s){
        return hash(s, s.length());
    }

    public static int hash(String s, int l){
        int res = 0;
        for (int i = 0; i < l; i++) {
            res = (s.charAt(i) + res * sigma)%mod;
        }
        return res;
    }

    public static  int nextHash(int prevHash, char prevChar, char nextChar){
        return (sigma *(prevHash - prevChar * h) + nextChar) % mod;
    }
    static int sigma = (int) Math.pow(2, 8);
    static int mod = (int) Math.pow(sigma,3);
    static int h = 0;
    public static void rabinCarp(String text, String pattern){
        h = BigInteger.valueOf(sigma).pow(pattern.length() -1).mod(BigInteger.valueOf(mod)).intValue();
        int patternHash = hash(pattern);
        int textHash = hash(text, pattern.length());
        for (int i = 0; i <= text.length() - pattern.length()  ; i++) {
                if(patternHash == textHash){
                    boolean spuriousHit = false;
                    for (int j = 0; j < pattern.length(); j++) {
                        if(pattern.charAt(j) != text.charAt(i + j)){
                            spuriousHit = true;
                            break;
                        }
                    }
                    if(spuriousHit){
                        System.out.println("SPURIOUS HIT");
                    } else {
                        System.out.println(i);
                    }
                }
                if(i >= text.length() - pattern.length()) break;
                textHash = nextHash(textHash, text.charAt(i), text.charAt(i + pattern.length()));
        }

    }
}