All geek questions in one place

Rearrange a string as a substring of another

For row A and another row B. Find if there is any permutation B as substring A.

For instance,

if A = "encyclopedia"

if B = "dep", then return true, since ped is a permutation of dep and ped is a substring of A.

My solution->

if length(A)=n and length(B)=m

I did this in 0((n-m+1)*m) by sorting B and then checking A 
with window size of m each time.

I need to find a better and faster solution.

+7
source share
10 answers

ASCII, O(n) O(1). , , true . printAllPermutations(). :

, , , . , :

S= {A_1,..., A_n} N, . S Q. S - N, Q.

- , . :

1 -> 1st prime
2 -> 2nd prime
3 -> 3rd prime
...
n -> nth prime

( , ASCII 256 ), B.

:

:

1: , A, smallHash.

2: 2 (Rightti Lefti). Rightti , Lefti A.

ex:     |  |
        v  v
       "abcdabcd"
        ^  ^
        |  |

3: currHash , B, () - 1.

4: justi, lefti 1, currHash, , , (lefti - 1), , , (Rightti)

5: , currHash smallHash, . .

6: , B. ( rightti B)

O(n) O(1) .

:

public class FindPermutationsInString {
    //This is an array containing the first 256 prime numbers
    static int primes[] = 
          {
            2,     3,     5,     7,    11,    13,    17,    19,    23,    29,
            31,    37,    41,    43,    47,    53,    59,    61,    67,    71,
            73,    79,    83,    89,    97,   101,   103,   107,   109,   113,
            127,   131,   137,   139,   149,   151,   157,   163,   167,   173,
            179,   181,   191,   193,   197,   199,   211,   223,   227,   229,
            233,   239,   241,   251,   257,   263,   269,   271,   277,   281,
            283,   293,   307,   311,   313,   317,   331,   337,   347,   349,
            353,   359,   367,   373,   379,   383,   389,   397,   401,   409,
            419,   421,   431,   433,   439,   443,   449,   457,   461,   463,
            467,   479,   487,   491,   499,   503,   509,   521,   523,   541,
            547,   557,   563,   569,   571,   577,   587,   593,   599,   601,
            607,   613,   617,   619,   631,   641,   643,   647,   653,   659,
            661,   673,   677,   683,   691,   701,   709,   719,   727,   733,
            739,   743,   751,   757,   761,   769,   773,   787,   797,   809,
            811,   821,   823,   827,   829,   839,   853,   857,   859,   863,
            877,   881,   883,   887,   907,   911,   919,   929,   937,   941,
            947,   953,   967,   971,   977,   983,   991,   997,  1009,  1013,
           1019,  1021,  1031,  1033,  1039,  1049,  1051,  1061,  1063,  1069,
           1087,  1091,  1093,  1097,  1103,  1109,  1117,  1123,  1129,  1151,
           1153,  1163,  1171,  1181,  1187,  1193,  1201,  1213,  1217,  1223,
           1229,  1231,  1237,  1249,  1259,  1277,  1279,  1283,  1289,  1291,
           1297,  1301,  1303,  1307,  1319,  1321,  1327,  1361,  1367,  1373,
           1381,  1399,  1409,  1423,  1427,  1429,  1433,  1439,  1447,  1451,
           1453,  1459,  1471,  1481,  1483,  1487,  1489,  1493,  1499,  1511,
           1523,  1531,  1543,  1549,  1553,  1559,  1567,  1571,  1579,  1583,
           1597,  1601,  1607,  1609,  1613,  1619
          };

    public static void main(String[] args) {
        String big = "abcdabcd";
        String small = "abcd";
        printAllPermutations(big, small);
    }

    static void printAllPermutations(String big, String small) {

        // If the big one is smaller than the small one,
        // there can't be any permutations, so return
        if (big.length() < small.length()) return;

        // Initialize smallHash to be the sum of the primes
        // corresponding to each of the characters in small.
        int smallHash = primeHash(small, 0, small.length());

        // Initialize righti and lefti.
        int lefti = 0, righti = small.length();

        // Initialize smallHash to be the sum of the primes
        // corresponding to each of the characters in big.
        int currentHash = primeHash(small, 0, righti);

        while (righti <= big.length()) {
            // If the current section of big is a permutation
            // of small, print it out.
            if (currentHash == smallHash)
                System.out.println(big.substring(lefti, righti));

            // Subtract the corresponding prime value in position
            // lefti. Then increment lefti
            currentHash -= primeHash(big.charAt(lefti++));

            if (righti < big.length()) // To prevent index out of bounds
                // Add the corresponding prime value in position righti.
                currentHash += primeHash(big.charAt(righti));

            //Increment righti.
            righti++;
        }

    }

    // Gets the sum of all the nth primes corresponding
    // to n being each of the characters in str, starting
    // from position start, and ending at position end - 1.
    static int primeHash(String str, int start, int end) {
        int value = 0;
        for (int i = start; i < end; i++) {
            value += primeHash(str.charAt(i));
        }
        return value;
    }

    // Get the n-th prime, where n is the ASCII value of chr
    static int primeHash(Character chr) {
        return primes[chr];
    }
}

, , , ASCII. , , int double. , , 1114112 .

+8

, j_random_hacker , O(|A|+|B|) : (: |A| " A".)

  • count, , 0 s.
  • distance 0
  • Bi B:
    • Decrement count[Bi].
    • count[Bi] 0, distance.
  • Ai A:
    • count[Ai]
    • i , |B| count[Ai-|B|].
    • count, 0, increment distance 0, distance.
    • , distance is 0, .

. , j_random_hacker, O(|A|+|B]), freqA freqB O(|alphabet|), . . , , , .

+7

, .

: n = A.size(), m = B.size()

.

B.

: B = "dep"

  • hash_B ['d'] = 1;
  • hash_B ['e'] = 1;
  • hash_B ['p'] = 1;

"A" "m".

: A = ""

'm' {e, n, c}. .

  • win ['e'] = 1
  • win ['n'] = 1
  • win ['c'] = 1

, (hash_B [] win []). . hash_B [] win [] 26.

, .

['e'] 1 ['y'] 1.

  • win ['n'] = 1
  • win ['c'] = 1
  • win ['y'] = 1

:

  • win ['p'] = 1;
  • win ['e'] = 1;
  • win ['d'] = 1;

, hash_B. , "" .

+6

. O (n) .

#include <stdio.h>
#include <string.h>

const char *a = "dep";
const char *b = "encyclopedia";

int cnt_a[26];
int cnt_b[26];

int main(void)
{
    const int len_a = strlen(a);
    const int len_b = strlen(b);

    for (int i = 0; i < len_a; i++) {
            cnt_a[a[i]-'a']++;
            cnt_b[b[i]-'a']++;
    }

    for (int i = 0; i < len_b-len_a; i++) {
            if (memcmp(cnt_a, cnt_b, sizeof(cnt_a)) == 0)
                    printf("%d\n", i);
            cnt_b[b[i]-'a']--;
            cnt_b[b[i+len_a]-'a']++;
    }

    return 0;
}
+1

true, B A.

public boolean isPermutedSubstring(String B, String A){
    int[] arr = new int[26];

    for(int i = 0 ; i < A.length();++i){
        arr[A.charAt(i) - 'a']++;
    }
    for(int j=0; j < B.length();++j){
        if(--arr[B.charAt(j)-'a']<0) return false;
    }
    return true;
}
+1

- ,

a: abbc b: cbabadcbbabbc a: abbc b: cbabadcbbabbc '__' '__' '__' For i-> b.len: sub = b.substring(i,i+len) isPermuted ? Java

class Test {
  public static boolean isPermuted(int [] asciiA, String subB){
    int [] asciiB = new int[26];

    for(int i=0; i < subB.length();i++){
      asciiB[subB.charAt(i) - 'a']++;
    }
    for(int i=0; i < 26;i++){
        if(asciiA[i] != asciiB[i])
        return false;
    }
    return true;
  }
  public static void main(String args[]){
    String a = "abbc";
    String b = "cbabadcbbabbc";
    int len = a.length();
    int [] asciiA = new int[26];
    for(int i=0;i<a.length();i++){
      asciiA[a.charAt(i) - 'a']++;
    }
    int lastSeenIndex=0;
    for(int i=0;i<b.length()-len+1;i++){
      String sub = b.substring(i,i+len);
      System.out.printf("%s,%s\n",sub,isPermuted(asciiA,sub));
} }
}
+1

, rici. https://wandbox.org/permlink/PdzyFvv8yDf3t69l , 1k . O (| A | + | B |), .

#include <string>

bool is_permuted_substring(std::string_view input_string,
                           std::string_view search_string) {
  if (search_string.empty()) {
    return true;
  }

  if (search_string.length() > input_string.length()) {
    return false;
  }

  int character_frequencies[256]{};
  auto distance = search_string.length();
  for (auto c : search_string) {
    character_frequencies[(uint8_t)c]++;
  }

  for (auto i = 0u; i < input_string.length(); ++i) {
    auto& cur_frequency = character_frequencies[(uint8_t)input_string[i]];
    if (cur_frequency > 0) distance--;
    cur_frequency--;

    if (i >= search_string.length()) {
      auto& prev_frequency = ++character_frequencies[(
          uint8_t)input_string[i - search_string.length()]];
      if (prev_frequency > 0) {
        distance++;
      }
    }

    if (!distance) return true;
  }

  return false;
}

int main() {
  auto test = [](std::string_view input, std::string_view search,
                 auto expected) {
    auto result = is_permuted_substring(input, search);
    printf("%s: is_permuted_substring(\"%.*s\", \"%.*s\") => %s\n",
           result == expected ? "PASS" : "FAIL", (int)input.length(),
           input.data(), (int)search.length(), search.data(),
           result ? "T" : "F");
  };

  test("", "", true);
  test("", "a", false);
  test("a", "a", true);
  test("ab", "ab", true);
  test("ab", "ba", true);
  test("aba", "aa", false);
  test("baa", "aa", true);
  test("aacbba", "aab", false);
  test("encyclopedia", "dep", true);
  test("encyclopedia", "dop", false);

  constexpr char negative_input[]{-1, -2, -3, 0};
  constexpr char negative_search[]{-3, -2, 0};
  test(negative_input, negative_search, true);

  return 0;
}
0

...

Cracking the Coding Interview, 6- № 70. , , O(n) time complexity (), , , .

# , - ...

, ( 100%), , O(n) time.

public int PermutationOfPatternInString(string text, string pattern)
{
    int matchCount = 0;
    Dictionary<char, int> charCount = new Dictionary<char, int>();
    int patLen = pattern.Length;
    foreach (char c in pattern)
    {
        if (charCount.ContainsKey(c))
        {
            charCount[c]++;
        }
        else
        {
            charCount.Add(c, 1);
        }
    }

    var subStringCharCount = new Dictionary<char, int>();

    // loop through each character in the given text (string)....
    for (int i = 0; i <= text.Length - patLen; i++)
    {
        // check if current char and current + length of pattern-th char are in the pattern.
        if (charCount.ContainsKey(text[i]) && charCount.ContainsKey(text[i + patLen - 1]))
        {
            string subString = text.Substring(i, patLen);
            int j = 0;
            for (; j < patLen; j++)
            {
                // there is no point going on if this subString doesnt contain chars that are in pattern...
                if (charCount.ContainsKey(subString[j]))
                {
                    if (subStringCharCount.ContainsKey(subString[j]))
                    {
                        subStringCharCount[subString[j]]++;
                    }
                    else
                    {
                        subStringCharCount.Add(subString[j], 1);
                    }
                }
                else
                {
                    // if any of the chars dont appear in the subString that we are looking for
                    // break this loop and continue...
                    break;
                }
            }

            int x = 0;

            // this will be true only when we have current subString permutation count
            // matched with pattern's.
            // we need this because the char count could be different 
            if (subStringCharCount.Count == charCount.Count)
            {
                for (; x < patLen; x++)
                {
                    if (subStringCharCount[subString[x]] != charCount[subString[x]])
                    {
                        // if any count dont match then we break from this loop and continue...
                        break;
                    }
                }
            }

            if (x == patLen)
            {
                // this means we have found a permutation of pattern in the text...
                // increment the counter.
                matchCount++;
            }

            subStringCharCount.Clear(); // clear the count map.
        }
    }

    return matchCount;
}

-...

[TestCase("encyclopedia", "dep", 1)]
[TestCase("cbabadcbbabbcbabaabccbabc", "abbc", 7)]
[TestCase("xyabxxbcbaxeabbxebbca", "abbc", 2)]
public void PermutationOfStringInText(string text, string pattern, int expectedAnswer)
{
    int answer = runner.PermutationOfPatternInString(text, pattern);
    Assert.AreEqual(expectedAnswer, answer);
}
0

O (TEXT.length) .

, . . , TRUE.

public static void main(String[] args) {
    String pattern = "dep";
    String text = "encyclopedia";
    System.out.println(isPermutationAvailable(pattern, text));
}

public static boolean isPermutationAvailable(String pattern, String text) {
    if (pattern.length() > text.length()) {
        return false;
    }
    int[] patternMap = new int[26];
    int[] textMap = new int[26];
    for (int i = 0; i < pattern.length(); i++) {
        patternMap[pattern.charAt(i) - 'a']++;
        textMap[text.charAt(i) - 'a']++;
    }
    int count = 0;
    for (int i = 0; i < 26; i++) {
        if (patternMap[i] == textMap[i]) {
            count++;
        }
    }
    for (int i = 0; i < text.length() - pattern.length(); i++) {
        int r = text.charAt(i + pattern.length()) - 'a';
        int l = text.charAt(i) - 'a';
        if (count == 26) {
            return true;
        }

        textMap[r]++;
        if (textMap[r] == patternMap[r]) {
            count++;
        }
        else if (textMap[r] == patternMap[r] + 1) {
            count--;
        }

        textMap[l]--;
        if (textMap[l] == patternMap[l]) {
            count++;
        }
        else if (textMap[l] == patternMap[l] - 1) {
            count--;
        }
    }
    return count == 26;
}
0

, @Ephraim .

. :

S= {A_1,..., A_n} N, . S Q. S N, Q.

, , C++ libgmpxx.

Under the assumption that the comparison between the two numbers is in O(1), then the solution is in O(|A| + |B|). The previous assumption may not really apply to those inputs where it |B|is large enough. When the |B| > |A|function returns to O(1).

Example:

#include <iostream>
#include <string>
#include <gmpxx.h>

static int primes[] =
          {
            2,     3,     5,     7,    11,    13,    17,    19,    23,    29,
            31,    37,    41,    43,    47,    53,    59,    61,    67,    71,
            73,    79,    83,    89,    97,   101,   103,   107,   109,   113,
            127,   131,   137,   139,   149,   151,   157,   163,   167,   173,
            179,   181,   191,   193,   197,   199,   211,   223,   227,   229,
            233,   239,   241,   251,   257,   263,   269,   271,   277,   281,
            283,   293,   307,   311,   313,   317,   331,   337,   347,   349,
            353,   359,   367,   373,   379,   383,   389,   397,   401,   409,
            419,   421,   431,   433,   439,   443,   449,   457,   461,   463,
            467,   479,   487,   491,   499,   503,   509,   521,   523,   541,
            547,   557,   563,   569,   571,   577,   587,   593,   599,   601,
            607,   613,   617,   619,   631,   641,   643,   647,   653,   659,
            661,   673,   677,   683,   691,   701,   709,   719,   727,   733,
            739,   743,   751,   757,   761,   769,   773,   787,   797,   809,
            811,   821,   823,   827,   829,   839,   853,   857,   859,   863,
            877,   881,   883,   887,   907,   911,   919,   929,   937,   941,
            947,   953,   967,   971,   977,   983,   991,   997,  1009,  1013,
           1019,  1021,  1031,  1033,  1039,  1049,  1051,  1061,  1063,  1069,
           1087,  1091,  1093,  1097,  1103,  1109,  1117,  1123,  1129,  1151,
           1153,  1163,  1171,  1181,  1187,  1193,  1201,  1213,  1217,  1223,
           1229,  1231,  1237,  1249,  1259,  1277,  1279,  1283,  1289,  1291,
           1297,  1301,  1303,  1307,  1319,  1321,  1327,  1361,  1367,  1373,
           1381,  1399,  1409,  1423,  1427,  1429,  1433,  1439,  1447,  1451,
           1453,  1459,  1471,  1481,  1483,  1487,  1489,  1493,  1499,  1511,
           1523,  1531,  1543,  1549,  1553,  1559,  1567,  1571,  1579,  1583,
           1597,  1601,  1607,  1609,  1613,  1619
          };

mpz_class prime_hash(std::string const &str, size_t start, size_t end)
{
    mpz_class hash(1);
    for (size_t i = start; i < end; ++i) {
        hash *= primes[(size_t) str.at(i)];
    }
    return hash;
}

void print_all_permutations(std::string const &big, std::string const &small)
{
    const size_t big_len = big.length();
    const size_t small_len = small.length();

    if (small_len <= 0 || big_len < small_len) {
        // no possible permutation!
        return;
    }

    // O(small_len)
    mpz_class small_hash = prime_hash(small, 0, small_len);
    mpz_class curr_hash = prime_hash(big, 0, small_len);

    // O(big_len)
    size_t left_idx = 0;
    do {

        if (curr_hash == small_hash) {
            std::cout << "Permutation '" << big.substr(left_idx, small_len)
                      << "' of '" << small
                      << "' at index " << left_idx
                      << " of '" << big
                      << "'." << std::endl;
        }

        curr_hash /= primes[(size_t) big.at(left_idx)];

        if (left_idx + small_len < big_len) {
            curr_hash *= primes[(size_t) big.at(left_idx + small_len)];
        }

        ++left_idx;

    } while (left_idx + small_len < big_len);
}

int main(int argc, char *argv[])
{
    // @user2826957 input
    print_all_permutations("encyclopedia", "dep");

    // @Ephraim input
    print_all_permutations("abcdabcd", "abcd");

    // @Sam input
    print_all_permutations("cbabadcbbabbc", "abbc");

    // @butt0s input
    print_all_permutations("", "");
    print_all_permutations("", "a");
    print_all_permutations("a", "");
    print_all_permutations("a", "a");

    return 0;
}

An example compiled with:

~$ g++ permstr.cpp -lgmpxx -lgmp -o run
~$ ./run
Permutation 'ped' of 'dep' at index 7 of 'encyclopedia'.
Permutation 'abcd' of 'abcd' at index 0 of 'abcdabcd'.
Permutation 'bcda' of 'abcd' at index 1 of 'abcdabcd'.
Permutation 'cdab' of 'abcd' at index 2 of 'abcdabcd'.
Permutation 'dabc' of 'abcd' at index 3 of 'abcdabcd'.
Permutation 'cbab' of 'abbc' at index 0 of 'cbabadcbbabbc'.
Permutation 'cbba' of 'abbc' at index 6 of 'cbabadcbbabbc'.
Permutation 'a' of 'a' at index 0 of 'a'.
0
source

Source: https://habr.com/ru/post/1534078/

More articles:


All Articles