假设我们有 字符串 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) 或更好的方法吗？
排序非常昂贵，并且不利用你用滑动窗口沿着 b 移动的事实。
我会使用位置无关的比较方法（因为任何排列都是有效的） - 为每个字母分配一个素数，每个字符串将是其字母值的乘积。
这样，当你遍历 b 时，每一步只需要除以你从左边删除的字母，然后乘以下一个字母。
您还需要说服自己，这确实与每个字符串唯一匹配并涵盖所有排列 - 这来自素数分解的唯一性。另请注意，在较大的字符串上，数字会变大，因此您可能需要一些用于大数字的库
不需要散列，您只需计算滑动窗口上的频率，并检查它是否匹配。假设你的字母表的大小是
sO(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
这几乎是解决方案，但会帮助您
countmade for only lower case chars该解决方案具有--
Time Complexity - O(L)Space Complexity - O(1)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;
}
编写一个函数 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 */
以下是我的解决方案。空间复杂度只是
O(a + b)O(b*a)bamd5的答案很好而且会更快！！
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-面试。最初的问题陈述类似于“找到 s 在 b 中的所有排列”。
使用 2 个哈希表，并且滑动窗口的大小 = 较小字符串的长度：
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;
}
另一种方法涉及使用带有字符计数字典的滑动窗口来匹配 B 中 S 的排列。
from collections import Counter
def find_permutations_in_string(S, B):
f1 = Counter(S)
len_s = len(S)
len_b = len(B)
res = []
if f1 == Counter(B[:len_s]):
res.append(0)
l, r = 1, len_s
while r < len_b:
f2 = Counter(B[l : r + 1])
if f1 == f2:
res.append(l)
l += 1
r += 1
return res
S = "abc"
B = "cbabcacab"
result = find_permutations_in_string(S, B)
print(result) # Output: [0, 2, 3, 6]
S = "abc"
B = "defghicba"
result = find_permutations_in_string(S, B)
print(result) # Output: [6]
S = "a"
B = "aaaaa"
result = find_permutations_in_string(S, B)
print(result) # Output: [0, 1, 2, 3, 4]
S = "abc"
B = "aabbcc"
result = find_permutations_in_string(S, B)
print(result) # Output: []