You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
19 lines
987 B
19 lines
987 B
非常棒的信奥题解！
|
|
https://blog.csdn.net/qq_44791484
|
|
|
|
https://www.cnblogs.com/newblg/p/14610243.html
|
|
鬼才想得到的解法
|
|
|
|
思路:
|
|
|
|
在验证某串a是否为b的子串时,常常使用kmp算法.当子串匹配下标j = 子串长度时,说明串a是串b的子串.如果i取到串b的最后一位时,j还没有 = a长度,说明a不是b的子串.
|
|
|
|
在这道题,我们需要构造串b,使得a不是b的子串,也就是j不能取到串a的长度.假设当前j是a的待匹配位,b的下一位构造位为i.第i位有26种取值,对于每个取值,j的下一步位置大多不同.将下一步的取值看成转化的状态的话,就能构造f[i][j]表示b构造了前i个字符,匹配了a子串的前j位.那么f[i][j] += f[i-1][k].
|
|
|
|
因为第i个字符是需要枚举a~z的,取到a[k]后要做一次kmp匹配,求第i位可以匹配的位置.
|
|
|
|
又一个优秀的博主
|
|
https://blog.csdn.net/qq_45832461?type=blog
|
|
https://www.cnblogs.com/zbsy-wwx/p/11742074.html
|
|
|