给定字符串A和另一个字符串B。查找任何B的排列是否存在作为A的子字符串。
例如，
如果A =“encyclopedia”
如果B ="dep"，则返回true，因为"ped"是“dep”的排列，并且"ped"是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.
我需要找到一个更好、更快的解决方案。
这个问题有一个更简单的解决方案。
这里：n = A.size()，m = B.size()
思路是使用哈希。
首先我们对字符串B中的字符进行哈希。
假设：B = "dep"
现在，我们针对字符串A的每个大小为m的窗口运行循环。
假设：A = "encyclopedia"
大小为'm'的第一个窗口将包含字符{e，n，c}。 我们现在将它们哈希。
现在我们检查两个数组（hash_B []和win []）中每个字符的频率是否相同。注意：hash_B []或win []的最大大小为26，因此复杂度将为O(26 * N) ~ O(N)。
如果它们不相同，我们就将窗口向右移动。
在移动窗口后，我们减少win ['e']的计数1并增加win ['y']的计数1。
在第七个转换期间，您的win数组状态为：
这与hash_B数组相同。 因此，打印"SUCCESS"并退出。
O（n）时间复杂度和O（1）空间复杂度内完成。我的代码还打印出了排列，但可以轻松修改为在第一次出现时返回true。代码的主要部分位于printAllPermutations()方法中。以下是我的解决方案：
这是我想出来的解决方案，与Rabin Karp算法的思想有些相似。在了解算法之前，我将如下解释其数学原理：
假设S = {A_1, ..., A_n} 是一个只包含质数的大小为N的multiset列表，让S中数字的总和等于某个整数Q。然后S是唯一可能完全由质数组成的大小为N的multiset，其元素之和可以等于Q。
因此，我们知道可以将每个字符映射到质数。我提出了以下映射：
1 -> 1st prime
2 -> 2nd prime
3 -> 3rd prime
...
n -> nth prime
ex: | |
v v
"abcdabcd"
^ ^
| |
3：创建变量currHash，并将其初始化为B中lefti和righti之间的每个字符所映射的对应素数之和。
4：同时将righti和lefti增加1，每次通过减去不再范围内（lefti-1）的字符所对应的素数并添加刚刚添加到范围（righti）中的字符所对应的素数来更新currHash。
5：每当currHash等于smallHash时，该范围内的字符必须是一个排列。然后我们打印它们。
6：继续直到我们到达B的末尾。（当righti等于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's the n-th prime, where n is the ASCII value of chr
static int primeHash(Character chr) {
return primes[chr];
}
}
请注意，这种解决方案仅适用于字符只能是ASCII字符的情况。如果我们谈论Unicode，则会涉及到超过int甚至double最大大小的质数。此外，我不确定是否有1,114,112个已知的质数。
O(|A|+|B|)，而是单变量的 O 吗？计算 smallHash 是 O(|B|)，遍历 A 是 O(|A|)。我喜欢这个解决方案，使用质数及其乘积进行哈希处理非常优雅。 - hnefatlC++ 实现。 - Patrick Trentin这个答案提出了一个由 @Ephraim 在他自己的答案中提出的想法的固定实现。
原始答案混淆了给定质数集合的乘法属性和加法。修正后的陈述应为：
设 S = {A_1, ..., A_n} 是一个大小为 N 的多重集合列表，其中仅包含质数。设 S 中数字的乘积等于某个整数 Q。那么 S 是唯一可能的完全由质数组成的大小为 N 的多重集合，其元素可以相乘得到Q。
为避免数值溢出，实现使用基于 C++ 库 libgmpxx 的无限精度算术。
在假设两个数字之间的比较是 O(1) 的情况下，该解决方案的时间复杂度为 O(|A| + |B|)。当输入中 |B| 足够大时，先前的假设实际上可能不成立。 当 |B| > |A| 时，该函数的返回时间复杂度为 O(1)。
示例：
#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's input
print_all_permutations("encyclopedia", "dep");
// @Ephraim's input
print_all_permutations("abcdabcd", "abcd");
// @Sam's 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;
}
这个例子是使用以下工具编译的：
~$ 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'.
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;
}
a: abbc
b: cbabadcbbabbc
然后逐个划下每个排列组合
a: abbc
b: cbabadcbbabbc
'__'
'__'
'__'
因此
对于 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));
} }
}
#include <stdio.h>
#include <string.h>
const char *a = "dep";
const char *b = "encyclopediaped";
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']++;
}
int i;
for (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']++;
}
if (memcmp(cnt_a, cnt_b, sizeof(cnt_a)) == 0)
printf("%d\n", i);
return 0;
}
这里有一个解决方案，基本上就是 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;
}
具有O(TEXT.length)的运行时间复杂度。
当计算出的文本值的平均值与计算出的模式值的平均值相匹配时，其中一些解决方案将无法工作。例如：uw和vv。尽管它们不匹配，但上面的某些解决方案仍会返回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;
}
我来晚了...
这个问题也在书中《破解程序员面试》第六版的第70页讨论过。作者说有可能使用O(n)时间复杂度（线性）找到所有排列，但她没有写出算法，所以我想试一试。
以下是C#解决方案，以防有人需要...
此外，我认为（不确定）它可以使用O(n)时间复杂度找到排列的数量。
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's 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);
}
- 在
- 对于A的每个长度为m的窗口，做同样的操作，但将它们存储在
- j_random_hackerfreqB [i]中累加字符i在字符串B中出现的次数。（例如，在您的示例中，freqB ['d'] == freqB ['e'] == freqB ['p'] == 1，对于所有其他字符i，freqB [i] == 0。）freqA []中，然后检查是否对于每个字符i，freqA[i] == freqB[i]。如果是这样，则表示匹配成功。要从从位置j开始的长度为m的窗口移动到下一个窗口，您需要执行--freqA[A[j]]和++freqA[A[j+m]]。