Description
月月和华华一起去吃饭了。期间华华有事出去了一会儿,没有带手机。月月出于人类最单纯的好奇心,打开了华华的手机。哇,她看到了一片的QQ推荐好友,似乎华华还没有浏览过。月月顿时醋意大发,出于对好朋友的关心,为了避免华华浪费太多时间和其他网友聊天,她要删掉一些推荐好友。但是为了不让华华发现,产生猜疑,破坏了他们的友情,月月决定只删华华有可能搭讪的推荐好友。
月月熟知华华搭讪的规则。华华想与某个小姐姐搭讪,当且仅当小姐姐的昵称是他的昵称的子序列。为了方便,华华和小姐姐的昵称只由小写字母构成。为了更加方便,保证小姐姐的昵称长度不会比华华的长。
现在月月要快速的判断出哪些推荐好友要删掉,因为华华快回来了,时间紧迫,月月有点手忙脚乱,所以你赶紧写个程序帮帮她吧!
Solution
如果这个题是子串而不是子序列的话那就是ac自动机裸题了。
如果是子序列的话就不需要构造自动机了。有一种叫双指针的算法,那么在这里面就可以套用成(n+1)指针法。
一开始所有的小姐姐昵称字符串的指针都放在最头。然后当华华昵称字符串的指针往后移动一格,倘若小姐姐昵称字符串的指针指向的是同一个字符,那么这些指针也跟着往后移动一格。
当小姐姐昵称字符串的指针指向’\0’这个字符时,就可以说这个字符串是华华昵称字符串的子序列了。
所以我们需要快速地找到当前指针指向的某个字符的字符串有哪些,可以对于每一个字符,都存有一个队列表示有哪些指针指向这个字符。这样总的复杂度就不会很高。
时间复杂度$O(|A|+\sum\limits_{i=1}^{n} |B_i|)$
但是很神奇的是,跑的比标程的$O(26\cdot|A|+\sum\limits_{i=1}^{n} |B_i|)$要慢。可能是我假了吧。
Code
1 |
|