Dynamic Programming and Fast Fourier Transform Approach for Polynomial Equation Models in Hash Collision Calculation

The hash polynomial of a string is defined by converting each letter in the string into a numerical value according to its position in the alphabet. In some cases, the number of strings that satisfy a given hash value is determined using a specified hash polynomial function. The number of possible character combinations and the repetition of subproblems that may occur present challenges in the given hash function. In this paper, we propose a novel solution to the aforementioned problem using dynamic programming technique and Fast Fourier Transform method, which satisfy a given polynomial hash function. In our algorithm, the recurrence relation for the dynamic programming technique utilizes polynomial equation model for each state. Therefore, for each transition in the recurrence relation, the values are updated through polynomial operations. One of these operations is polynomial multiplication, where the Fast Fourier Transform (FFT) is used to speed up computation. Based on test results from a given case study, the dynamic programming approach and Fast Fourier Transform achieves an average execution time of 2.62 seconds and consumes an average of 19 MB of memory, utilizing only 1.23% of the available memory limit.