字符串 2 的 Anagram 是字符串 1 的子字符串
Anagram of String 2 is Substring of String 1
如何找到字符串 1 的任意变位词是字符串 2 的子字符串？
例如：-
字符串 1 =超过
字符串 2=计算器
所以它将 return 为真，因为 "rove" 的变位词是 "over"，它是字符串 2
的子字符串
您可能需要创建 String1 的所有可能组合，如 rove、rvoe、reov..然后检查此组合是否在 String2 中。
它可以在 O(n^3) 预处理中完成，每个查询 O(klogk) 其中： n 是 "given string" 的大小（您的示例中的字符串 2 ) 并且 k 是查询的大小（您的示例中的字符串 1）。
预处理：
For each substring s of string2: //O(n^2) of those
sort s
store s in some data base (hash table, for example)
查询：
given a query q:
sort q
check if q is in the data base
if it is - it's an anagram of some substring
otherwise - it is not.
此答案假定您要为单个字符串（字符串 2）检查多个 "queries"（字符串 1），从而尝试优化每个查询的复杂性。
如评论中所述，您可以懒惰地执行前处理步骤 - 这意味着，当您第一次遇到长度为 k 的查询时，将长度为 k 的所有子字符串插入 DS，并按照最初的建议进行。
令 L 为 String1 的长度。
遍历 String2 并检查每个长度为 L 的子字符串是否是 String1 的变位词。
在您的示例中，String1 = rove 和 String2 = Whosebug。
stackoverflow
stac 和 rove 不是变位词，所以移动到下一个长度为 L 的子串。
stackoverflow
tack 和 rove 不是变位词，依此类推直到找到子字符串。
一种更快的方法是检查当前子字符串中的最后一个字母是否出现在 String1 中，即，一旦您发现 stac 和 rove 不是变位词，并且看到 'c'（这是最后一个当前子串的字母）在 rove 中不存在，您可以简单地完全跳过该子串并从 'k'.
获取下一个子串
即stackoverflow
stac 和 rove 不是变位词。 'c' 不存在于 'rove' 中，因此只需跳过此子字符串并从 'k':
开始检查
stackoverflow
这将显着减少比较次数。
编辑：
这是上述方法的 Python2 实现。
注意： 此实现的工作假设是两个字符串中的所有字符均为小写并且它们仅由字符 a -z 组成。
def isAnagram(s1, s2):
c1 = [0] * 26
c2 = [0] * 26
# increase character counts for each string
for i in s1:
c1[ord(i) - 97] += 1
for i in s2:
c2[ord(i) - 97] += 1
# if the character counts are same, they are anagrams
if c1 == c2:
return True
return False
def isSubAnagram(s1, s2):
l = len(s1)
# s2[start:end] represents the substring in s2
start = 0
end = l
while(end <= len(s2)):
sub = s2[start:end]
if isAnagram(s1, sub):
return True
elif sub[-1] not in s1:
start += l
end += l
else:
start += 1
end += 1
return False
输出：
>>> print isSubAnagram('rove', 'Whosebug')
True
>>> print isSubAnagram('rowe', 'Whosebug')
False
编辑：在最坏的情况下，我的第一个答案是二次方的。我已将其调整为严格线性：
这是一种基于滑动概念的方法window：创建一个字典，该字典以第一个字典的字母为键，其中包含相应值的字母频率计数。将其视为需要与第二个字符串中的 m 个连续字母匹配的目标字典，其中 m 是第一个字符串的长度。
首先处理第二个字符串中的前 m 个字母。对于每个这样的字母，如果它在目标字典中显示为键 将相应的值减少 1。目标是将所有目标值驱动为 0。将 discrepancy 定义为处理 m 个字母的第一个 window 之后的值的绝对值之和。
重复执行以下操作：检查是否 discrepancy == 0 和 return True 如果是。否则——取 m 个字母前的字符并检查它是否是目标键，如果是——将值增加 1。在这种情况下，这会将差异增加或减少 1，并相应地进行调整。然后获取第二个字符串的下一个字符并对其进行处理。检查它是否是字典中的键，如果是，则适当调整值和差异。
由于没有嵌套循环，每次通过主循环只涉及一些字典查找、比较、加法和减法，所以整个算法是线性的。
A Python 3 实现（展示了 window 滑动和目标计数和差异调整的基本逻辑）：
def subAnagram(s1,s2):
m = len(s1)
n = len(s2)
if m > n: return false
target = dict.fromkeys(s1,0)
for c in s1: target[c] += 1
#process initial window
for i in range(m):
c = s2[i]
if c in target:
target[c] -= 1
discrepancy = sum(abs(target[c]) for c in target)
#repeatedly check then slide:
for i in range(m,n):
if discrepancy == 0:
return True
else:
#first process letter from m steps ago from s2
c = s2[i-m]
if c in target:
target[c] += 1
if target[c] > 0: #just made things worse
discrepancy +=1
else:
discrepancy -=1
#now process new letter:
c = s2[i]
if c in target:
target[c] -= 1
if target[c] < 0: #just made things worse
discrepancy += 1
else:
discrepancy -=1
#if you get to this stage:
return discrepancy == 0
典型输出：
>>> subAnagram("rove", "stack overflow")
True
>>> subAnagram("rowe", "stack overflow")
False
为了对其进行压力测试，我从 Project Gutenberg 下载了 Moby Dick 的全文。这有超过 100 万个字符。书中提到 "Formosa"，因此 "moors" 的变位词作为 Moby Dick 的子字符串出现。但是，毫不奇怪，"Whosebug" 的变位词没有出现在 Moby Dick:
>>> f = open("moby dick.txt")
>>> md = f.read()
>>> f.close()
>>> len(md)
1235186
>>> subAnagram("moors",md)
True
>>> subAnagram("Whosebug",md)
False
最后一次调用大约需要 1 秒来处理 Moby Dick 的完整文本并验证其中没有出现 "Whosebug" 的变位词。
//Two string are considered and check whether Anagram of the second string is
//present in the first string as part of it (Substring)
//e.g. 'atctv' 'cat' will return true as 'atc' is anagram of cat
//Similarly 'battex' is containing an anagram of 'text' as 'ttex'
public class SubstringIsAnagramOfSecondString {
public static boolean isAnagram(String str1, String str2){
//System.out.println(str1+"::" + str2);
Character[] charArr = new Character[str1.length()];
for(int i = 0; i < str1.length(); i++){
char ithChar1 = str1.charAt(i);
charArr[i] = ithChar1;
}
for(int i = 0; i < str2.length(); i++){
char ithChar2 = str2.charAt(i);
for(int j = 0; j<charArr.length; j++){
if(charArr[j] == null) continue;
if(charArr[j] == ithChar2){
charArr[j] = null;
}
}
}
for(int j = 0; j<charArr.length; j++){
if(charArr[j] != null)
return false;
}
return true;
}
public static boolean isSubStringAnagram(String firstStr, String secondStr){
int secondLength = secondStr.length();
int firstLength = firstStr.length();
if(secondLength == 0) return true;
if(firstLength < secondLength || firstLength == 0) return false;
//System.out.println("firstLength:"+ firstLength +" secondLength:" + secondLength+
//" firstLength - secondLength:" + (firstLength - secondLength));
for(int i = 0; i < firstLength - secondLength +1; i++){
if(isAnagram(firstStr.substring(i, i+secondLength),secondStr )){
return true;
}
}
return false;
}
public static void main(String[] args) {
System.out.println("isSubStringAnagram(xyteabc,ate): "+ isSubStringAnagram("xyteabc","ate"));
}
}
如何找到字符串 1 的任意变位词是字符串 2 的子字符串？
例如：-
字符串 1 =超过
字符串 2=计算器
所以它将 return 为真，因为 "rove" 的变位词是 "over"，它是字符串 2
的子字符串您可能需要创建 String1 的所有可能组合，如 rove、rvoe、reov..然后检查此组合是否在 String2 中。
它可以在 O(n^3) 预处理中完成，每个查询 O(klogk) 其中： n 是 "given string" 的大小（您的示例中的字符串 2 ) 并且 k 是查询的大小（您的示例中的字符串 1）。
预处理：
For each substring s of string2: //O(n^2) of those
sort s
store s in some data base (hash table, for example)
查询：
given a query q:
sort q
check if q is in the data base
if it is - it's an anagram of some substring
otherwise - it is not.
此答案假定您要为单个字符串（字符串 2）检查多个 "queries"（字符串 1），从而尝试优化每个查询的复杂性。
如评论中所述，您可以懒惰地执行前处理步骤 - 这意味着，当您第一次遇到长度为 k 的查询时，将长度为 k 的所有子字符串插入 DS，并按照最初的建议进行。
令 L 为 String1 的长度。
遍历 String2 并检查每个长度为 L 的子字符串是否是 String1 的变位词。
在您的示例中，String1 = rove 和 String2 = Whosebug。
stackoverflow
stac 和 rove 不是变位词，所以移动到下一个长度为 L 的子串。
stackoverflow
tack 和 rove 不是变位词，依此类推直到找到子字符串。
一种更快的方法是检查当前子字符串中的最后一个字母是否出现在 String1 中，即，一旦您发现 stac 和 rove 不是变位词，并且看到 'c'（这是最后一个当前子串的字母）在 rove 中不存在，您可以简单地完全跳过该子串并从 'k'.
获取下一个子串即stackoverflow
stac 和 rove 不是变位词。 'c' 不存在于 'rove' 中，因此只需跳过此子字符串并从 'k':
开始检查stackoverflow
这将显着减少比较次数。
编辑：
这是上述方法的 Python2 实现。
注意： 此实现的工作假设是两个字符串中的所有字符均为小写并且它们仅由字符 a -z 组成。
def isAnagram(s1, s2):
c1 = [0] * 26
c2 = [0] * 26
# increase character counts for each string
for i in s1:
c1[ord(i) - 97] += 1
for i in s2:
c2[ord(i) - 97] += 1
# if the character counts are same, they are anagrams
if c1 == c2:
return True
return False
def isSubAnagram(s1, s2):
l = len(s1)
# s2[start:end] represents the substring in s2
start = 0
end = l
while(end <= len(s2)):
sub = s2[start:end]
if isAnagram(s1, sub):
return True
elif sub[-1] not in s1:
start += l
end += l
else:
start += 1
end += 1
return False
输出：
>>> print isSubAnagram('rove', 'Whosebug')
True
>>> print isSubAnagram('rowe', 'Whosebug')
False
编辑：在最坏的情况下，我的第一个答案是二次方的。我已将其调整为严格线性：
这是一种基于滑动概念的方法window：创建一个字典，该字典以第一个字典的字母为键，其中包含相应值的字母频率计数。将其视为需要与第二个字符串中的 m 个连续字母匹配的目标字典，其中 m 是第一个字符串的长度。
首先处理第二个字符串中的前 m 个字母。对于每个这样的字母，如果它在目标字典中显示为键 将相应的值减少 1。目标是将所有目标值驱动为 0。将 discrepancy 定义为处理 m 个字母的第一个 window 之后的值的绝对值之和。
重复执行以下操作：检查是否 discrepancy == 0 和 return True 如果是。否则——取 m 个字母前的字符并检查它是否是目标键，如果是——将值增加 1。在这种情况下，这会将差异增加或减少 1，并相应地进行调整。然后获取第二个字符串的下一个字符并对其进行处理。检查它是否是字典中的键，如果是，则适当调整值和差异。
由于没有嵌套循环，每次通过主循环只涉及一些字典查找、比较、加法和减法，所以整个算法是线性的。
A Python 3 实现（展示了 window 滑动和目标计数和差异调整的基本逻辑）：
def subAnagram(s1,s2):
m = len(s1)
n = len(s2)
if m > n: return false
target = dict.fromkeys(s1,0)
for c in s1: target[c] += 1
#process initial window
for i in range(m):
c = s2[i]
if c in target:
target[c] -= 1
discrepancy = sum(abs(target[c]) for c in target)
#repeatedly check then slide:
for i in range(m,n):
if discrepancy == 0:
return True
else:
#first process letter from m steps ago from s2
c = s2[i-m]
if c in target:
target[c] += 1
if target[c] > 0: #just made things worse
discrepancy +=1
else:
discrepancy -=1
#now process new letter:
c = s2[i]
if c in target:
target[c] -= 1
if target[c] < 0: #just made things worse
discrepancy += 1
else:
discrepancy -=1
#if you get to this stage:
return discrepancy == 0
典型输出：
>>> subAnagram("rove", "stack overflow")
True
>>> subAnagram("rowe", "stack overflow")
False
为了对其进行压力测试，我从 Project Gutenberg 下载了 Moby Dick 的全文。这有超过 100 万个字符。书中提到 "Formosa"，因此 "moors" 的变位词作为 Moby Dick 的子字符串出现。但是，毫不奇怪，"Whosebug" 的变位词没有出现在 Moby Dick:
>>> f = open("moby dick.txt")
>>> md = f.read()
>>> f.close()
>>> len(md)
1235186
>>> subAnagram("moors",md)
True
>>> subAnagram("Whosebug",md)
False
最后一次调用大约需要 1 秒来处理 Moby Dick 的完整文本并验证其中没有出现 "Whosebug" 的变位词。
//Two string are considered and check whether Anagram of the second string is
//present in the first string as part of it (Substring)
//e.g. 'atctv' 'cat' will return true as 'atc' is anagram of cat
//Similarly 'battex' is containing an anagram of 'text' as 'ttex'
public class SubstringIsAnagramOfSecondString {
public static boolean isAnagram(String str1, String str2){
//System.out.println(str1+"::" + str2);
Character[] charArr = new Character[str1.length()];
for(int i = 0; i < str1.length(); i++){
char ithChar1 = str1.charAt(i);
charArr[i] = ithChar1;
}
for(int i = 0; i < str2.length(); i++){
char ithChar2 = str2.charAt(i);
for(int j = 0; j<charArr.length; j++){
if(charArr[j] == null) continue;
if(charArr[j] == ithChar2){
charArr[j] = null;
}
}
}
for(int j = 0; j<charArr.length; j++){
if(charArr[j] != null)
return false;
}
return true;
}
public static boolean isSubStringAnagram(String firstStr, String secondStr){
int secondLength = secondStr.length();
int firstLength = firstStr.length();
if(secondLength == 0) return true;
if(firstLength < secondLength || firstLength == 0) return false;
//System.out.println("firstLength:"+ firstLength +" secondLength:" + secondLength+
//" firstLength - secondLength:" + (firstLength - secondLength));
for(int i = 0; i < firstLength - secondLength +1; i++){
if(isAnagram(firstStr.substring(i, i+secondLength),secondStr )){
return true;
}
}
return false;
}
public static void main(String[] args) {
System.out.println("isSubStringAnagram(xyteabc,ate): "+ isSubStringAnagram("xyteabc","ate"));
}
}