use*_*957 7 string algorithm substring permutation
给定一个字符串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.
我需要找到一个更好,更快的解决方案.
如果我只需要担心ASCII字符,可以O(n)及时用O(1)空格完成.我的代码也打印出排列,但可以很容易地修改为只在第一个实例返回true.代码的主要部分位于printAllPermutations()方法中.这是我的解决方案:
这是我提出的解决方案,它有点类似于Rabin Karp算法背后的想法.在我理解算法之前,我将解释它背后的数学如下:
设S = {A_1,...,A_n}是大小为N的多集列表,仅包含素数.让S中的数字之和等于某个整数Q.然后小号是大小唯一可能完全素多重集Ñ,其元素可以总结到Q.
因此,我们知道我们可以将每个字符映射到素数.我提出如下地图:
1 -> 1st prime
2 -> 2nd prime
3 -> 3rd prime
...
n -> nth prime
如果我们这样做(我们可以因为ASCII只有256个可能的字符),那么我们很容易在较大的字符串B中找到每个排列.
我们将执行以下操作:
1:计算A中每个字符映射到的素数之和,我们称之为smallHash.
2:创建2个指数(righti和lefti).righti初始化为零,lefti初始化为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,我们开始进入超过inta或甚至a 的最大大小的素数double.另外,我不确定有1,114,112个已知素数.
通过j_random_hacker在注释中提供的算法构建一点,有可能找到匹配O(|A|+|B|),如下:(注意:在整个过程中,我们|A|用来表示"长度A".)
count其域是字母表的大小,初始化为所有0s.distance为0BiBcount[Bi]count[Bi]0distanceAiAcount[Ai]i大于|B|减量.count[Ai-|B|]count修改的两个值中的每一个,如果前一个值为0,则递增distance,如果新值0则递减distance.distance则0找到匹配.注意:所提出的算法j_random_hacker也是O(|A|+|B])因为freqA与之比较的成本freqB是O(|alphabet|),这是一个常数.但是,上述算法将比较成本降低到一个小常数.此外,理论上可以通过使用未初始化数组的标准技巧,即使字母表不是恒定大小也可以使其工作.
这个问题有一个更简单的解决方案,可以在线性时间内完成.
这里:n = A.size(),m = B.size()
想法是使用散列.
首先我们散列字符串B的字符.
假设:B = " dep "
现在我们为每个大小为' m '的窗口在字符串' A '上运行一个循环.
假设:A ="百科全书"
第一个大小为'm'的窗口将包含字符{e,n,c}.我们现在将哈希.
现在我们检查两个数组(hash_B []和win [])中每个字符的频率是否相同.注意:hash_B []或win []的最大大小为26.
如果他们不一样,我们会转移窗口.
移位窗口后,我们减少的计由1胜["E"]和增加的计由1胜["Y"] .
在第七班期间,您的胜利阵列的状态是:
与hash_B数组相同.所以,打印"SUCCESS"并退出.