Dart语言中contains方法所用字符串搜索算法名称及细节咨询

你贴出的代码是Dart里List类型的contains实现，并不是字符串（String）的contains方法，下面分别说明两者的算法细节：

一、你贴的List.contains：线性搜索（顺序搜索） #

这段代码是典型的线性搜索（也叫顺序搜索），逻辑非常直接：

• 从列表第一个元素开始，逐个和目标元素对比
• 找到匹配项就立刻返回true，不用遍历完整个列表
• 额外加了并发修改校验：遍历过程中如果列表长度变了，就抛出ConcurrentModificationError，防止列表结构变化导致遍历出问题
• 时间复杂度：最好情况O(1)（第一个元素就匹配），最坏情况O(n)（没找到或最后一个元素匹配），平均复杂度O(n)

二、String.contains的搜索算法 #

Dart字符串的contains方法做子串搜索时，底层会根据子串长度选择优化后的算法：

• 如果是短子串（一般长度≤3），会用优化的线性搜索——因为复杂算法的预处理成本比直接遍历更高，反而不划算
• 如果是较长子串，默认用Boyer-Moore-Horspool算法（Boyer-Moore算法的简化版），它通过跳过不可能匹配的位置减少比较次数，实际场景里效率比线性搜索高很多，最坏时间复杂度是O(n*m)（n是主串长度，m是子串长度），但平均表现优秀

要是你给String.contains传的是正则表达式（RegExp），那会用正则引擎的匹配算法，就不是上面的子串搜索逻辑了。

内容的提问来源于stack exchange，提问作者Apuja19