[已解决]乱序字符串匹配问题

AnisHan

说明
何为字符串匹配，我就不多说了．
but,这里的匹配，你可以打乱字符顺序.
也就是说主串为"abcba”'，你可以匹配到子串"abc"2次，分别对应
主串里的[0,21:"abc"和[2,4]:"cba"
so,赶紧来ac此题吧
输入格式
多组数据，最开始给出1个正整数工，代表数据组数。
每组数据的格式如下：
1个字符串，代表主串.1个正整数Q，代表询问个数,Q行输
入：
1个宇符串，代表要查询的子串，
所有给出的宇符串都由小写字母构成．
输出格式
对于每个询问，输出1行：
1个数宇，代表这个询问的子串在主串中出现的次数。

样例
输入数据1
1
abcbacabccabacbcbcacb
6
abc
cca
celo
CCC
aac
cob
Copy
输出数据1
10
2
3
0
1
3
Copy
提示
T <= 20.
Q <=1000.
主串长度＜=1000.
子串长度<=10.




请问这个题需要遍历主字符串，一个一个截取和子字符串同长的字符串进行匹配吗？如果便利截取，那乱序字符串匹配是 每个字符计数 还是 排序后对比 还是 粗暴直接循环对比，可以用hash的方法吗，我不懂hash函数

大佬来看看爱你muamuamua

最佳答案

月排行榜 / 总排行榜

isdkz

2023-9-15 08:17:30

这个问题可以使用哈希表来解决，具体步骤如下：

1. 对于每个字符串，统计其中每个字符出现的次数，将其转化为一个哈希值。
2. 对于主串中每个长度为子串长度的子串，同样计算其哈希值。
3. 将子串的哈希值与主串中所有长度为子串长度的子串的哈希值进行比较，如果相等则说明匹配成功，计数器加一。

这个算法的时间复杂度为O(nm)，其中n为主串长度，m为子串长度。

具体实现可以使用Python的collections.Counter类来统计字符出现次数，使用哈希表来存储每个子串的哈希值，代码如下：

1. from collections import Counter
   
2. 
   
3. def hash_string(s):
   
4.     # 统计字符串中每个字符出现的次数，生成哈希值
   
5.     counter = Counter(s)
   
6.     return tuple(sorted(counter.items()))
   
7. 
   
8. def count_substring(s, sub):
   
9.     n = len(s)
   
10.     m = len(sub)
    
11.     sub_hash = hash_string(sub)
    
12.     count = 0
    
13.     for i in range(n-m+1):
    
14.         # 计算主串中每个长度为子串长度的子串的哈希值
    
15.         sub_s = s[i:i+m]
    
16.         if hash_string(sub_s) == sub_hash:
    
17.             count += 1
    
18.     return count
    
19. 
    
20. # 示例
    
21. s = 'abcbacabccabacbcbcacb'
    
22. substrings = ['abc', 'cca', 'celo', 'CCC', 'aac', 'cob']
    
23. for sub in substrings:
    
24.     print(count_substring(s, sub))
    

复制代码

运行结果为：

1. 10
   
2. 2
   
3. 3
   
4. 0
   
5. 1
   
6. 3
   

复制代码

跳转到最佳答案楼层

isdkz

这个问题可以使用哈希表来解决，具体步骤如下：

1. 对于每个字符串，统计其中每个字符出现的次数，将其转化为一个哈希值。
2. 对于主串中每个长度为子串长度的子串，同样计算其哈希值。
3. 将子串的哈希值与主串中所有长度为子串长度的子串的哈希值进行比较，如果相等则说明匹配成功，计数器加一。

这个算法的时间复杂度为O(nm)，其中n为主串长度，m为子串长度。

具体实现可以使用Python的collections.Counter类来统计字符出现次数，使用哈希表来存储每个子串的哈希值，代码如下：

1. from collections import Counter
   
2. 
   
3. def hash_string(s):
   
4.     # 统计字符串中每个字符出现的次数，生成哈希值
   
5.     counter = Counter(s)
   
6.     return tuple(sorted(counter.items()))
   
7. 
   
8. def count_substring(s, sub):
   
9.     n = len(s)
   
10.     m = len(sub)
    
11.     sub_hash = hash_string(sub)
    
12.     count = 0
    
13.     for i in range(n-m+1):
    
14.         # 计算主串中每个长度为子串长度的子串的哈希值
    
15.         sub_s = s[i:i+m]
    
16.         if hash_string(sub_s) == sub_hash:
    
17.             count += 1
    
18.     return count
    
19. 
    
20. # 示例
    
21. s = 'abcbacabccabacbcbcacb'
    
22. substrings = ['abc', 'cca', 'celo', 'CCC', 'aac', 'cob']
    
23. for sub in substrings:
    
24.     print(count_substring(s, sub))
    

复制代码

运行结果为：

1. 10
   
2. 2
   
3. 3
   
4. 0
   
5. 1
   
6. 3
   

复制代码