给定一个字符串A和另一个字符串B.查找B的任何排列是否作为A的子字符串存在。
例如，
如果A =“百科全书”
如果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.
我需要找到一个更好，更快的解决方案。
在j_random_hacker的评论中建立一点算法，可以在O(|A|+|B|)中找到匹配，如下所示:(注意：在整个过程中，我们使用|A|来表示“A的长度”。）
count，其域是字母表的大小，初始化为所有0s。distance设为0Bi中的每个角色B：
减少count[Bi]。
如果以前的count[Bi]计数是0，也增加distance。Ai中的每个角色A：
增加count[Ai]
如果i大于|B|减少count[Ai-|B|]。
对于修改的两个count值中的每一个，如果前一个值是0，则增加distance，如果新值是0，则递减distance。
如果结果是distance是0，则找到匹配。注意：由j_random_hacker提出的算法也是O(|A|+|B])，因为比较freqA和freqB的成本是O(|alphabet|)，这是一个常数。但是，上述算法将比较成本降低到一个小常数。此外，理论上可以通过使用未初始化数组的标准技巧，即使字母表不是恒定大小也可以使其工作。
如果我只需要担心ASCII字符，可以使用O(n)空间在O(1)时间内完成。我的代码也打印出排列，但可以很容易地修改为只在第一个实例返回true。代码的主要部分位于printAllPermutations()方法中。这是我的解决方案：
这是我提出的解决方案，它有点类似于Rabin Karp算法背后的想法。在我理解算法之前，我将解释它背后的数学如下：
设S = {A_1，...，A_n}是大小为N的multiset列表，仅包含素数。设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个指数（righti和lefti）。 right初始化为零，left初始化为A的大小。
ex: | |
v v
"abcdabcd"
^ ^
| |
3：创建一个变量currHash，并将其初始化为B中每个字符，（包括）righti和lefti-1之间映射到的相应素数之和。
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个已知素数。
这个问题有一个更简单的解决方案，可以在线性时间内完成。
这里：n = A.size（），m = B.size（）
想法是使用散列。
首先我们散列字符串B的字符。
假设：B =“dep”
现在我们为每个大小为'm'的窗口在字符串'A'上运行一个循环。
假设：A =“百科全书”
第一个大小为'm'的窗口将包含字符{e，n，c}。我们现在将哈希。
现在我们检查两个数组（hash_B []和win []）中每个字符的频率是否相同。注意：hash_B []或win []的最大大小为26。
如果他们不一样，我们会转移窗口。
移动窗口后，我们将win ['e']的数量减少1，并将win ['y']的数量增加1。
在第七班期间，您的胜利阵列的状态是：
与hash_B数组相同。所以，打印“SUCCESS”并退出。
上述谈话清楚了这个想法。具有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;
}
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));
} }
}
如果String B是String A的置换子串，则下面的函数将返回true。
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;
}
这是一个非常有效的解决方案。 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;
}
我迟到了这个派对......
这个问题也在第70页的名为Cracking the Coding Interview, 6th Edition的书中讨论过。作者说有可能使用O(n) time complexity（线性）找到所有的排列，但她没有编写算法，所以我认为我应该试一试。
这是C＃解决方案，以防万一有人在寻找......
此外，我认为（不是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'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);
}
采用O（TEXT.length）运行时复杂性。
当计算的文本值的平均值与计算的模式值的平均值匹配时，这些解决方案中的一些将不起作Ex - 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;
}