Optimize rabin-karp algortihm

42 Views Asked by At

I have a task : "Jewish-style carp"

Devise a version of Rabin-Karp algorithm which will check if for a given
picture* M by N large its top-right K by K corner is duplicated somewhere in the picture.
Your algorithm should replace slow modulo prime operations with faster bitwise mask &'s.
!!!! Do make sure that the RT is at most linear in the number of pixels in the text !!!

* Here, picture is a two-dimensional array of arbitrary items.

and I write the code m= mask value and B= Base value

public static boolean hasDuplicateCorner(int[][] picture, int K) {
        int M = (1 << K) - 1; // Mask value
        int B = 31; // Base value

        Map<Integer, Boolean> hashTable = new HashMap<>();

        // Compute hash value of the top-right KxK corner
        int cornerHash = 0;
        for (int row = 0; row < K; row++) {
            for (int col = picture[row].length - K; col < picture[row].length; col++) {
                cornerHash = ((cornerHash << 1) + picture[row][col]) & M;
            }
        }
        hashTable.put(cornerHash, true);

        // Iterate over the remaining elements of the picture
        for (int row = 0; row <= picture.length - K; row++) {
            for (int col = 0; col <= picture[row].length - K; col++) {
                // Compute hash value of the current KxK corner
                int currentHash = 0;
                for (int i = row; i < row + K; i++) {
                    for (int j = col; j < col + K; j++) {
                        currentHash = ((currentHash << 1) + picture[i][j]) & M;
                    }
                }
                // Check if the current hash value already exists in the hash table
                if (hashTable.containsKey(currentHash)) {
                    return true; // Duplicate corner found
                }
                // Add the current hash value to the hash table
                hashTable.put(currentHash, true);
            }
        }

        return false; // No duplicate corner found
    }

but it didn't work for all inputs.

How can I solve this problem, and I asked AI but it didn't work too

0

There are 0 best solutions below