【基础】子串的个数
子串是指在一个字符串中连续的字符序列。对于一个长度为n的字符串，它的子串个数为n*(n+1)/2。本文将介绍基础算法来计算子串个数，并讨论一些优化方法的性能和效果。
一、基础算法
子串个数的基础算法很简单，只需要枚举每个子串的开头和结尾，然后统计出这些子串就可以了。具体实现如下：
```python def count_substrings(s):    n = len(s)    cnt = 0    for i in range(n):        for j in range(i, n):            cnt += 1    return cnt ```
该算法的时间复杂度为O(n^2)，当字符串较大时，它可能会用尽所有的内存和计算资源，而无法得到结果。因此，需要考虑优化算法的性能和效果。
二、优化算法
1. 中心扩展算法
字符串长度就是字符串中字符的个数
中心扩展算法是一种优化算法，用于计算给定字符串的所有回文子串。回文子串是指从左到右和从右到左都相同的子串。中心扩展算法的思想是，从字符串中的每个字符开始，向左和向右扩展，直到遇到不同的字符为止。具体实现如下：
```python def count_substrings(s):    n = len(s)    cnt = 0    for i in range(n):        # odd length palindromes        l, r = i, i        while l >= 0 and r < n and s[l] == s[r]:            cnt += 1            l -= 1            r += 1        # even length palindromes        l, r = i, i+1        while l >= 0 and r < n and s[l] == s[r]:            cnt += 1            l -= 1            r += 1    return cnt ```
该算法的时间复杂度为O(n^2)，但是由于它只处理回文子串，因此其实际运行时间要比基础算法快。
2. Rabin-Karp算法
Rabin-Karp算法是一种高效的字符串匹配算法，它通过哈希函数计算子串的哈希值，然后比较目标字符串中每个子串的哈希值，以便到匹配的字符串。具体实现如下：
```python def count_substrings(s):    n = len(s)    p = 31    m = 10**9 + 9    hash = [0] * (n+1)
    pow = [1] * (n+1)    cnt = 0    for i in range(1, n+1):        hash[i] = (hash[i-1] * p + ord(s[i-1])) % m        pow[i] = pow[i-1] * p % m    for i in range(n):        for j in range(i, n):            h = (hash[j+1] - hash[i] * pow[j-i+1]) % m            if h == 0:                cnt += 1    return cnt ```
该算法的时间复杂度为O(n^2)，但是由于它使用哈希函数计算子串的哈希值，因此其实际运行时间要比基础算法快。
三、总结
子串个数的基础算法的时间复杂度为O(n^2)，可能会用尽所有的内存和计算资源，因此需要考虑优化算法的性能和效果。其中，中心扩展算法是一种优化算法，用于计算给定字符串的所有回文子串；Rabin-Karp算法是一种高效的字符串匹配算法，它使用哈希函数计算子串的哈希值，并比较目标字符串中每个子串的哈希值，以便到匹配的字符串。这些算法都以优异的性能和效果著称，不同的算法选择是取决于实际情况的。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。