Количество подстрок, которые являются анаграммой любой подстроки другой строки

Опубликовано: 5 Января, 2022

Учитывая две строки S1 и S2 , задача состоит в том, чтобы подсчитать количество подстрок S1, которые являются анаграммами любой подстроки S2 .

Примеры:

Input: S1 = “ABB”, S2 = “BAB”
Output: 5
There are 6 sub-strings of S1 : “A”, “B”, “B”, “AB”, “BB” and “ABB”
Out of which only “BB” is the one which is not an anagram of any sub-string of S2.
Input: S1 = “PLEASEHELPIMTRAPPED”, S2 = “INAKICKSTARTFACTORY”
Output: 9

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Наивный подход: простой подход - проверить все подстроки S1 на соответствие всем подстрокам S2 , являются ли они анаграммами или нет.

Эффективный подход: возьмите все подстроки S1 одну за другой, скажем temp, и проверьте, является ли temp анаграммой какой-либо подстроки S2 , вычислив частоты всех символов temp и сравнив их с частотами символов подстроки. строки S2, имеющие длину = длина (темп) .
Это можно сделать с помощью одного обхода, взяв первые символы длины (временные) из S2, а затем для каждой итерации добавить частоту следующего символа строки и удалить частоту первого символа ранее выбранной подстроки. пока не будет пройдена вся строка.

Ниже представлена реализация описанного выше подхода:

C ++

 // C++ program to find the number of sub-strings
 // of s1 which are anagram of any sub-string of s2
 
#include <bits/stdc++.h>
 using namespace std;
 
#define ALL_CHARS 256
 
// This function returns true if
 // contents of arr1[] and arr2[]
 // are same, otherwise false.
 bool compare( char * arr1, char * arr2)
 {
    for ( int i = 0; i < ALL_CHARS; i++)
        if (arr1[i] != arr2[i])
            return false ;
 
    return true ;
 }
 
// This function search for all permutations
 // of string pat[] in string txt[]
 bool search(string pat, string txt)
 {
    int M = pat.length();
    int N = txt.length();
 
    int i;
 
    // countP[]: Store count of all characters
    // of pattern
    // countTW[]: Store count of current
    // window of text
    char countP[ALL_CHARS] = { 0 };
    char countTW[ALL_CHARS] = { 0 };
    for (i = 0; i < M; i++) {
        (countP[pat[i]])++;
        (countTW[txt[i]])++;
    }
 
    // Traverse through remaining
    // characters of pattern
    for (i = M; i < N; i++) {
 
        // Compare counts of current
        // window of text with
        // counts of pattern[]
        if (compare(countP, countTW)) {
            // cout<<pat<<" "<<txt<<" ";
            return true ;
        }
 
        // Add current character to current window
        (countTW[txt[i]])++;
 
        // Remove the first character
        // of previous window
        countTW[txt[i - M]]--;
    }
 
    // Check for the last window in text
    if (compare(countP, countTW))
        return true ;
 
    return false ;
 }
 
// Function to return the number of sub-strings of s1
 // that are anagrams of any sub-string of s2
 int calculatesubString(string s1, string s2, int n)
 {
    // initializing variables
    int count = 0, j = 0, x = 0;
 
    // outer loop for picking starting point
    for ( int i = 0; i < n; i++) {
 
        // loop for different length of substrings
        for ( int len = 1; len <= n - i; len++) {
 
            // If s2 has any substring which is
            // anagram of s1.substr(i, len)
            if (search(s1.substr(i, len), s2)) {
 
                // increment the count
                count = count + 1;
            }
        }
    }
    count; return
 }
 
// Driver code
 int main()
 {
    string str1 = "PLEASEHELPIMTRAPPED" ;
    string str2 = "INAKICKSTARTFACTORY" ;
 
    int len = str1.length();
 
    cout << calculatesubString(str1, str2, len);
 
    return 0;
 }

Джава

 // Java program to find the number of sub-Strings
 // of s1 which are anagram of any sub-String of s2
 class GFG {
 
    static int MAX_LEN = 1005 ;
    static int MAX_CHAR = 26 ;
 
    static int ALL_CHARS = 256 ;
 
    // This function returns true if
    // contents of arr1[] and arr2[]
    // are same, otherwise false.
    static boolean compare( char [] arr1, char [] arr2)
    {
        for ( int i = 0 ; i < ALL_CHARS; i++)
            if (arr1[i] != arr2[i])
                return false ;
 
        return true ;
    }
 
    // This function search for all permutations
    // of String pat[] in String txt[]
    static boolean search(String pat, String txt)
    {
        int M = pat.length();
        int N = txt.length();
 
        int i;
 
        // countP[]: Store count of all characters
        // of pattern
        // countTW[]: Store count of current
        // window of text
        char countP[] = new char [ALL_CHARS];
        char countTW[] = new char [ALL_CHARS];
        for (i = 0 ; i < M; i++) {
            (countP[pat.charAt(i)])++;
            (countTW[txt.charAt(i)])++;
        }
 
        // Traverse through remaining
        // characters of pattern
        for (i = M; i < N; i++) {
 
            // Compare counts of current
            // window of text with
            // counts of pattern[]
            if (compare(countP, countTW)) {
                // cout<<pat<<" "<<txt<<" ";
                return true ;
            }
 
            // Add current character to current window
            (countTW[txt.charAt(i)])++;
 
            // Remove the first character
            // of previous window
            countTW[txt.charAt(i - M)]--;
        }
 
        // Check for the last window in text
        if (compare(countP, countTW))
            return true ;
 
        return false ;
    }
 
    // Function to return the number of sub-Strings of s1
    // that are anagrams of any sub-String of s2
    static int calculatesubString(String s1, String s2, int n)
    {
        // initializing variables
        int count = 0 , j = 0 , x = 0 ;
 
        // outer loop for picking starting point
        for ( int i = 0 ; i < n; i++) {
 
            // loop for different length of subStrings
            for ( int len = 1 ; len <= n - i; len++) {
 
                // If s2 has any subString which is
                // anagram of s1.substr(i, len)
                if (search(s1.substring(i, i + len), s2)) {
 
                    // increment the count
                    count = count + 1 ;
                }
            }
        }
        count; return
    }
 
    // Driver code
    public static void main(String args[])
    {
        String str1 = "PLEASEHELPIMTRAPPED" ;
        String str2 = "INAKICKSTARTFACTORY" ;
 
        int len = str1.length();
 
        System.out.println(calculatesubString(str1, str2, len));
    }
 }
 
// This code has been contributed by 29AjayKumar

Python3

 # Python3 program to find the number of sub-strings
 # of s1 which are anagram of any sub-string of s2
 ALL_CHARS = 256
 
# This function returns true if
 # contents of arr1[] and arr2[]
 # are same, otherwise false.
 def compare(arr1, arr2):
    for i in range (ALL_CHARS):
        if arr1[i] ! = arr2[i]:
            return False
    return True
 
# This function search for all permutations
 # of string pat[] in string txt[]
 def search(pat, txt):
    M = len (pat)
    N = len (txt)
 
    # countP[]: Store count of all characters
    # of pattern
    # countTW[]: Store count of current
    # window of text
    countP = [ 0 ] * ALL_CHARS
    countTW = [ 0 ] * ALL_CHARS
    for i in range (M):
        countP[ ord (pat[i])] + = 1
        countTW[ ord (txt[i])] + = 1
 
    # Traverse through remaining
    # characters of pattern
    for i in range (M, N):
 
        # Compare counts of current
        # window of text with
        # counts of pattern[]
        if compare(countP, countTW):
            return True
 
        # Add current character to current window
        countTW[ ord (txt[i])] + = 1
 
        # Remove the first character
        # of previous window
        countTW[ ord (txt[i - M])] - = 1
 
    # Check for the last window in text
    if compare(countP, countTW):
        return True
 
    return False
 
# Function to return the number of sub-strings of s1
 # that are anagrams of any sub-string of s2
 def calculateSubString(s1, s2, n):
 
    # initializing variables
    count, j, x = 0 , 0 , 0
 
    # outer loop for picking starting point
    for i in range (n):
 
        # loop for different length of substrings
        for length in range ( 1 , n - i + 1 ):
 
            # If s2 has any substring which is
            # anagram of s1.substr(i, len)
            if search(s1[i:i + length], s2):
 
                # increment the count
                count + = 1
 
    count return
 
# Driver Code
 if __name__ = = "__main__" :
    str1 = "PLEASEHELPIMTRAPPED"
    str2 = "INAKICKSTARTFACTORY"
 
    length = len (str1)
 
    print (calculateSubString(str1, str2, length))
 
# This code is contributed by
 # sanjeev2552

C #

 // C# program to find the number of sub-Strings
 // of s1 which are anagram of any sub-String of s2
 using System;
 using System.Collections.Generic;
 
class GFG {
 
    static int MAX_LEN = 1005;
    static int MAX_CHAR = 26;
 
    static int ALL_CHARS = 256;
 
    // This function returns true if
    // contents of arr1[] and arr2[]
    // are same, otherwise false.
    static bool compare( char [] arr1, char [] arr2)
    {
        for ( int i = 0; i < ALL_CHARS; i++)
            if (arr1[i] != arr2[i])
                return false ;
 
        return true ;
    }
 
    // This function search for all permutations
    // of String pat[] in String txt[]
    static bool search(String pat, String txt)
    {
        int M = pat.Length;
        int N = txt.Length;
 
        int i;
 
        // countP[]: Store count of all characters
        // of pattern
        // countTW[]: Store count of current
        // window of text
        char [] countP = new char [ALL_CHARS];
        char [] countTW = new char [ALL_CHARS];
        for (i = 0; i < M; i++) {
            (countP[pat[i]])++;
            (countTW[txt[i]])++;
        }
 
        // Traverse through remaining
        // characters of pattern
        for (i = M; i < N; i++) {
 
            // Compare counts of current
            // window of text with
            // counts of pattern[]
            if (compare(countP, countTW)) {
                // cout<<pat<<" "<<txt<<" ";
                return true ;
            }
 
            // Add current character to current window
            (countTW[txt[i]])++;
 
            // Remove the first character
            // of previous window
            countTW[txt[i - M]]--;
        }
 
        // Check for the last window in text
        if (compare(countP, countTW))
            return true ;
 
        return false ;
    }
 
    // Function to return the number of sub-Strings of s1
    // that are anagrams of any sub-String of s2
    static int calculatesubString(String s1, String s2, int n)
    {
        // initializing variables
        int count = 0, j = 0, x = 0;
 
        // outer loop for picking starting point
        for ( int i = 0; i < n; i++) {
 
            // loop for different length of subStrings
            for ( int len = 1; len <= n - i; len++) {
 
                // If s2 has any subString which is
                // anagram of s1.substr(i, len)
                if (search(s1.Substring(i, len), s2)) {
 
                    // increment the count
                    count = count + 1;
                }
            }
        }
        count; return
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String str1 = "PLEASEHELPIMTRAPPED" ;
        String str2 = "INAKICKSTARTFACTORY" ;
 
        int len = str1.Length;
 
        Console.WriteLine(calculatesubString(str1, str2, len));
    }
 }
 
/* This code contributed by PrinciRaj1992 */

Выход:

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Technical Scripter Алгоритмы Структуры данных

Количество подстрок, которые являются анаграммой любой подстроки другой строки

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

C ++

Джава

Python3

C #

РЕКОМЕНДУЕМЫЕ СТАТЬИ