算法——找出字符串a在字符串b中的所有排列

Question

假设我们有字符串 a = "abc" 字符串 b = "abcdcabaabccbaa"

找出a在b中所有排列的位置。我正试图为此找到一个有效的算法。

伪代码：

sort string a // O(a loga)

for windows of length a in b  // O(b)?
   sort that window of b      // O(~a loga)?
   compare to a
   if equal
      save the index

那么这是一个正确的算法吗？运行时间大概是 O(aloga + ba loga) ~= O(a loga b)？这有多有效？可能减少到 O(a*b) 或更好的方法？

Answer 1

排序是非常昂贵的，并且不使用你沿着 b 滑动移动的事实 window。

我会使用与位置无关的比较方法（因为任何排列都是有效的）- 为每个字母分配一个素数，每个字符串将是其字母值的乘积。

这样，当你遍历 b 时，每一步只需要除以你从他左边删除的字母，然后乘以下一个字母。

您还需要说服自己，这确实对每个字符串唯一匹配并涵盖所有排列——这来自质数分解的唯一性。另请注意，在较大的字符串上，数字会变大，因此您可能需要一些用于大数字的库

Answer 2

写一个函数strcount()来计算字符串或子字符串str中字符ch的出现次数

然后只需传递搜索字符串即可。

  for(i=0;i<haystacklenN-NeedleN+1;i++)
  {
    for(j=0;j<needleN;j++)
       if(strcount(haystack + i, Nneedle, needle[j]) != strcount(needles, needlesN, needle[j])
        break
  }
  if(j == needleN)
         /* found a permuatation */

Answer 3

不需要哈希，你可以计算你滑动的频率window，然后检查它是否匹配。假设你的字母表的大小是 s，你会得到一个非常简单的 O(s(n + m)) 算法。

// a = [1 .. m] and b = [1 .. n] are the input
cnta = [1 .. s] array initialized to 0
cntb = [1 .. s] array initialized to 0
// nb_matches = the number of i s.t. cnta[i] = cntb[i]
// thus the current subword = a iff. nb_matches = s
nb_matches = s

for i = 1 to m:
    if cntb[a[i]] = 0: nb_matches -= 1
    cntb[a[i]] += 1

ans = 0
for i = 1 to n:
    if cntb[b[i]] = cnta[b[i]]: nb_matches -= 1
    cntb[b[i]] += 1
    if nb_matches = s: ans += 1
    if cntb[b[i]] = cnta[b[i]]: nb_matches += 1
    if i - m + 1 >= 1:
        if cntb[b[i - m + 1]] = cnta[b[i - m + 1]]: nb_matches -= 1
        cntb[b[i - m + 1]] += 1
        if cntb[b[i - m + 1]] = cnta[b[i - m + 1]]: nb_matches += 1
        cntb[b[i - m + 1]] -= 1
return ans

Answer 4

以下是我的解决方案。 space 复杂度仅为 O(a + b)，而运行时间（如果我可以正确计算的话..）为 O(b*a)，至于 b 中的每个字符，我们可以进行递归 a 层深度。

md5的回答很好，会更快！！

public class FindPermutations {
public static void main(String[] args) {

    System.out.println(numPerms(new String("xacxzaa"),
            new String("fxaazxacaaxzoecazxaxaz")));
    System.out.println(numPerms(new String("ABCD"),
            new String("BACDGABCDA")));
    System.out.println(numPerms(new String("AABA"),
            new String("AAABABAA")));

    // prints 4, then 3, then 3
}

public static int numPerms(final String a, final String b) {
    int sum = 0;
    for (int i = 0; i < b.length(); i++) {
        if (permPresent(a, b.substring(i))) {
            sum++;
        }
    }
    return sum;
}

// is a permutation of a present at the start of b?
public static boolean permPresent(final String a, final String b) {
    if (a.isEmpty()) {
        return true;
    }

    if (b.isEmpty()) {
        return false;
    }

    final char first = b.charAt(0);
    if (a.contains(b.substring(0, 1))) {
        // super ugly, but removes first from a
        return permPresent(a.substring(0, a.indexOf(first)) + a.substring(a.indexOf(first)+1, a.length()),
                b.substring(1));
    }
    return false;
}
}

为了便于搜索，我在寻找其他解决方案与我的进行比较后到达此页面，问题源于观看此剪辑：https://www.hackerrank.com/domains/tutorials/cracking-the-coding-interview。最初的问题陈述类似于 'find all permutations of s in b'.

Answer 5

使用 2 个散列表和滑动 window 大小 = 较小字符串的长度：

int premutations_of_B_in_A(string large, string small) {
    unordered_map<char, int> characters_in_large;
    unordered_map<char, int> characters_in_small;
    int ans = 0;

    for (char c : small) {
        characters_in_small[c]++;
    }
    for (int i = 0; i < small.length(); i++) {
        characters_in_large[large[i]]++;
        ans += (characters_in_small == characters_in_large);
    }
    for (int i = small.length(); i < large.length(); i++) {
        characters_in_large[large[i]]++;
        if (characters_in_large[large[i - small.length()]]-- == 1)
            characters_in_large.erase(large[i - small.length()]);

        ans += (characters_in_small == characters_in_large);
    }
    return ans;
}

Answer 6

这几乎是解决方案，但可以帮助您 count 将小字符串排列成更大的字符串

made for only lower case chars

这个解决方案有--

Time Complexity - O(L) 其中 L 是提供给问题的大输入的长度，确切地说，对于大数组中存在的每个字符也包括 26，但忽略常数项，我将完全支持这一点。

Space Complexity - O(1) 因为 26 也是常数并且与输入的大小无关。

int findAllPermutations(string small, string larger) {
    int freqSmall[26] = {0};
    //window size
    int n = small.length();

    //to return
    int finalAns = 0;

    for (char a : small) {
        freqSmall[a - 97]++;
    }

    int freqlarger[26]={0};
    int count = 0;
    int j = 0;

    for (int i = 0; larger[i] != '[=10=]'; i++) {
        freqlarger[larger[i] - 97]++;
        count++;

        if (count == n) {
            count = 0;
            int i;
            for (i = 0; i < 26; i++) {
                if (freqlarger[i] != freqSmall[i]) {
                    break;
                }
            }
            if (i == 26) {
                finalAns++;
            }
            freqlarger[larger[j] - 97]--;
             j++;
        }

    }
    return finalAns;
}

int main() {
    string s, t;
    cin >> s >> t;
    cout << findAllPermutations(s, t) << endl;
    return 0;
}

算法——找出字符串a在字符串b中的所有排列

Algorithm - find all permutations of string a in string b

sorting

algorithm

permutation