算法 - 在字符串b中找到所有包含字符串a的排列组合

Question

算法 - 在字符串b中找到所有包含字符串a的排列组合

6

假设有以下字符串：

string a = "abc"
string b = "abcdcabaabccbaa"

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

伪代码:

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) 或更好的复杂度？

- Bao Thai

排序的时间复杂度是O(n)从什么时候开始的？ - Leeor

抱歉，我已经纠正了。不过我对大O符号并不很熟悉。@Leeor - Bao Thai

@Leeor：一个字符串通常属于一个小字母表，因此使用计数排序对其进行排序是O(n+s)... - md5

6个回答

2

无需进行哈希，您可以在滑动窗口上仅计算频率并检查是否匹配。假设您的字母表大小为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

- md5

这是什么符号表示？ - Ben Creasy

1

这几乎是一个解决方案，但可以帮助你计算较大字符串中较小字符串的排列出现的次数。

仅适用于小写字符。

该解决方案具有以下特点：

时间复杂度为O(L)，其中L是提供给问题的大输入的长度。确切地说，对于每个在大数组中出现的字符，还应包括26，但通过忽略常数项，我将仅代表这一部分。

空间复杂度为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] != '\0'; 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;
}

- Ritik Sharma

4

感谢您提供这段代码片段，它可能为一些有限的短期帮助提供了一些支持。通过展示为什么这是一个好的解决方案，适当的解释会极大地提高它的长期价值，并使其对未来有类似问题的读者更有用。请编辑您的答案添加一些解释，包括您所做出的假设。 - Toby Speight

0

使用两个哈希表和大小为较小字符串长度的滑动窗口：

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;
}

- Saksham Tikoo

0

以下是我的解决方案。空间复杂度只有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。原始问题陈述大致是“在 b 中查找 s 的所有排列”。

- gorbot

0

编写一个函数 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 */

- Malcolm McLean

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Leeor · Accepted Answer

排序非常耗费时间，并且不利用你通过滑动窗口沿着 b 移动的事实。

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

这样，当你遍历 b 时，每个步骤只需要通过左侧删除的字母除以它，并与下一个字母相乘。

您还需要确信这确实唯一地匹配每个字符串并涵盖所有排列-这源于质数分解的唯一性。同时请注意，在较大的字符串上，数字变得很大，因此您可能需要一些处理大数的库。