String Hashing

Problem Statement

You are given ‘N’ string. Write a program to check whether all the strings are distinct or not using string hashing.

Algorithm

• Define a function hashing():
  • Function details:
    • Takes string ‘S’ as a parameter.
    • This function returns the hash value of ‘S’.
  • Working: 
    • Create variable ANS = 0.
    • Create variable P = 1.
    • Create variable M = 10e9 +7.
    • Iterate loop for each character of string:
      • ANS += (S[i] - 'a') * P;
      • P *= 31;
    • Return ‘ANS’.
• Call the hashing function for all strings and store their hash values in the array.
• Sort the array.
• Check whether the adjacent hash values are equal or not.

Program

// Program to check whether all the strings are distinct or not using string hashing.
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// Function to find the hash of string.
int hashing(string s)
{
    // To store the hash value.
    int ans = 0;

    // To store 'P'.
    int p = 1;

    // For taking modulo.
    int m = 1000000007;
    for (int i = 0; i < s.size(); i++)
    {
        ans += (s[i] - 'a') * p;
        ans = ans % m;
        p *= 31;
    }
    return ans;
}

int main()
{

    // Taking number of strings as input.
    int n;
    cin >> n;

    // Taking strings as an input.
    vector<pair<int, string>> vec(n);
    for (int i = 0; i < n; i++)
    {
        string temp;
        cin >> temp;

        // Function call.
        vec[i].first = hashing(temp);
        vec[i].second = temp;
    }

    // Sort the vector.
    sort(vec.begin(), vec.end());
    int i;
    for (i = 0; i < n - 1; i++)
    {
        if (vec[i] == vec[i + 1])
        {
            break;
        }
    }
    if (i == n - 1)
        cout << "All strings are distinct";
    else
        cout << "All strings are not distinct";
}

You can also try this code with Online C++ Compiler

Run Code

Input 1

4
cat
bat
cat
gat

Output 1

All strings are not distinct

Input 2

4
cat
bat
gat

Output 2

All strings are distinct

Time Complexity

O(N * K), where ‘N’ is the number of strings and ‘K’ is the maximum length of string among them.
Hashing function traverses each character of the string, which takes O(K) time. And total number of strings is N. Hence total time complexity for this program is O(N * K).

Space Complexity

O(1).
As we didn’t use extra space except for a few variables.
Check out this problem - Longest String Chain

Also Read - hash function in data structure

Key Takeaways

In this blog, we learned the concept of string hashing, hash function, and collision. We have started with the discussion of string hashing. After that, we have seen how hash value is calculated, and then we have seen the difficulties we face, i.e., collision and how collision can be reduced.

Therefore learning never stops, and there is a lot more to learn.

Recommended problems -

• Find the Shortest Substring in a String
• Subsequence of a String
• Beautiful String
• Palindrome string

So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!