题解 | 最长公共子串

### 基于哈希表的最长公共子串优化解法

您提出的思路非常精妙，这是一种利用哈希表优化动态规划的方法。核心思想是通过预处理 `str2` 的字符位置信息，避免不必要的比较操作。下面我将详细说明这种方法的实现和复杂度分析。

#### 核心思路
1. **预处理**：为 `str2` 构建哈希表，记录每个字符出现的所有位置
2. **状态转移**：遍历 `str1` 时，对于每个字符，只检查其在 `str2` 中的实际出现位置
3. **连续性约束**：要求 `str2` 中的索引必须连续递增（+1）

#### 算法实现
```python
from collections import defaultdict

def longest_common_substring(str1, str2):
if not str1 or not str2:
return ""

# 构建str2的字符位置索引
char_positions = defaultdict(list)
for idx, char in enumerate(str2):
char_positions[char].append(idx)

# 使用字典存储状态：key=当前索引，value=连续匹配长度
dp = {}
max_len = 0
end_pos = 0# 记录在str1中的结束位置

for i, char in enumerate(str1):
new_dp = {}
# 只处理当前字符在str2中实际出现的位置
for j in char_positions[char]:
# 检查前一个位置是否连续
if j > 0 and j - 1 in dp:
length = dp[j - 1] + 1
else:
length = 1

new_dp[j] = length

# 更新全局最大值
if length > max_len:
max_len = length
end_pos = i

dp = new_dp# 更新状态

start = end_pos - max_len + 1
return str1[start:end_pos + 1] if max_len > 0 else ""
```

#### 时间复杂度分析
令：
- `n = len(str1)`
- `m = len(str2)`
- `d(c) = char_positions[c]` 的大小（字符 `c` 在 `str2` 中的出现次数）

**时间复杂度**：`O(n × avg(d))`
其中 `avg(d)` 是字符在 `str2` 中平均出现次数：
1. **最佳情况**（字符分布均匀）：`avg(d) ≈ m/|Σ|`（Σ 是字符集大小）
- 时间复杂度：`O(n × m/|Σ|)`
2. **最坏情况**（所有字符相同）：`avg(d) = m`
- 时间复杂度：`O(n × m)`（退化为标准DP）
3. **平均情况**：取决于实际字符分布

#### 空间复杂度
- **哈希表**：`O(m)` 存储所有字符位置
- **状态字典**：最坏 `O(m)`，但实际只存储可能匹配的位置
- **总空间复杂度**：`O(m)`

#### 算法优势
1. **避免无效比较**：只检查实际可能匹配的位置
2. **自适应优化**：性能随字符分布变化：
- 字符集越大（如Unicode文本），优势越明显
- 重复字符越少，优势越明显
3. **连续性约束**：自然满足公共子串的连续性要求

#### 对比标准DP
| 指标| 标准DP| 哈希优化DP|
|-------------|---------------|-----------------------|
| 时间复杂度| `O(n×m)`| `O(n×avg(d))`|
| 空间复杂度| `O(min(n,m))` | `O(m)`|
| 最佳情况| `O(n×m)`| `O(n×m/|Σ|)`|
| 最坏情况| `O(n×m)`| `O(n×m)`（相同）|
| 适用场景| 通用| 字符集大、重复率低的文本 |

这种方法的本质是通过空间换时间，利用预处理信息跳过不可能匹配的位置，在字符分布有利的场景下能显著提升性能。