假设模式P和文本T是长度分别为m和n的随机选取的字符串，其字

[问答题]

假设模式P和文本T是长度分别为m和n的随机选取的字符串，其字符分别来自含有d个元素的字母表 $\sum_{d}^{}{}$ {0，1, .，d-1},其中d $\geq$ 2。证明朴素算法第4行中隐含的循环所执行的字符比较的预计次数为:

直到这次循环结束。(假设对于一个给定的偏移，当有一个字符不匹配或者整个模式已被匹配时，朴素算法将终止字符比较。)因此，对任意随机选取的字符串，朴素算法都是有效的。

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小

难度：

0条回答 0收藏 361浏览

扫一扫，把题目装进口袋