字符串作为另一个子字符串的排列 [英] Permutation of string as substring of another
问题描述
给出一个字符串A和另一个字符串B.查找B的任何排列是否作为A的子字符串存在.
Given a string A and another string B. Find whether any permutation of B exists as a substring of A.
例如，
如果A =百科全书"
if A = "encyclopedia"
如果B ="dep"则返回true，因为ped是dep的排列，而ped是A的子串.
if B="dep" then return true as ped is a permutation of dep and ped is a substring of 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.
我需要找到一个更好，更快的解决方案.
I need to find a better and a faster solution.
推荐答案
如果我只需要担心ASCII字符，则可以在O(n)时间内用O(1)空格完成.我的代码也可以打印出排列，但是可以很容易地对其进行修改，以使其在第一个实例处简单地返回true.代码的主要部分位于printAllPermutations()方法中.这是我的解决方案:
If I only have to worry about ASCII characters, it can be done in O(n) time with O(1) space. My code also prints the permutations out, but can be easily modified to simply return true at the first instance instead. The main part of the code is located in the printAllPermutations() method. Here is my solution:
这是我想出的一个解决方案，它与Rabin Karp算法背后的思想有点相似.在理解算法之前，我将解释其背后的数学运算，如下所示:
This is a solution that I came up with, it is somewhat similar to the idea behind the Rabin Karp Algorithm. Before I understanding the algorithm, I will explain the math behind it as follows:
让 S = {A_1，...，A_n}是多集大小为 N 的列表，其中仅包含质数.令S中的数字之和等于某个整数 Q .然后， S 是唯一可能的大小为 N 的完全素数多重集，其元素的总和为 Q .
Let S = {A_1, ..., A_n} be a multiset list of size N that contains only prime numbers. Let the sum of the numbers in S equal some integer Q. Then S is the only possible entirely prime multiset of size N, whose elements can sum to Q.
因此，我们知道我们可以将每个字符映射到素数.我提出了如下地图:
Because of this, we know we can map every character to a prime number. I propose a map as follows:
1 -> 1st prime
2 -> 2nd prime
3 -> 3rd prime
...
n -> nth prime
如果执行此操作(因为ASCII仅具有256个可能的字符，我们可以这样做)，那么我们很容易在较大的字符串B中找到每个排列.
If we do this (which we can because ASCII only has 256 possible characters), then it becomes very easy for us to find each permutation in the larger string B.
我们将执行以下操作:
1:计算A中每个字符映射到的素数之和，我们称它为smallHash.
1: calculate the sum of the primes mapped to by each of the characters in A, let's call it smallHash.
2:创建2个索引(righti和lefti). righti初始化为零，lefti初始化为A的大小.
2: create 2 indices (righti and lefti). righti is initialized to zero, and lefti is initialzed to the size of A.
ex: | |
v v
"abcdabcd"
^ ^
| |
3:创建一个变量currHash，并将其初始化为在(包括)righti和lefti-1之间的B中每个字符映射到的对应质数的总和.
3: Create a variable currHash, and initialize it to the sum of the corresponding prime numbers mapped to by each of the characters in B, between (inclusive) righti, and lefti - 1.
4:每次对righti和lefti进行1迭代，每次更新currHash的方法是，从不再在范围内的字符(lefti-1)中减去映射的质数，并添加与刚刚添加到该范围中的字符相对应的质数(righti)
4: Iterate both righti and lefti by 1, each time updating currHash by subtracting the prime mapped from the character that is no longer in the range (lefti - 1) and adding the prime corresponding to the character just added to the range (righti)
5:每次currHash等于smallHash时，范围内的字符必须是一个排列.所以我们将它们打印出来.
5: Each time currHash is equal to smallHash, the characters in the range must be a permutation. So we print them out.
6:继续直到我们到达B的末尾.(当righti等于B的长度时)
6: Continue until we have reached the end of B. (When righti is equal to the length of B)
此解决方案在O(n)时间复杂度和O(1)空间中运行.
This solution runs in O(n) time complexity and O(1) space.
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个已知质数.
Keep in mind, however, that this solution only works when the characters can only be ASCII characters. If we are talking about unicode, we start getting into prime numbers that exceed the maximum size of an int, or even a double. Also, I'm not sure that there are 1,114,112 known primes.
这篇关于字符串作为另一个子字符串的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
