传送门
思路
唉,我太弱了,什么都不会,连 KMP 也不会,WA 飞了,唉,我太弱啦!
首先,原始的 KMP 算法实际上求的是 border 数组,即题目中说的前缀等于后缀的最长长度。我们考虑如何计算不管重叠的 num 数组。
显然的是,可以不断地令 cnt = f[cnt]
,直到 cnt = 0
。这样跳跃的次数就是这个位置的 num。但是这么做显然会超时,显然这个可以递推,因此我们递推就好了,时间复杂度为
O
(
n
)
O(n)
O(n)。
现在考虑重叠。一个显然的思路是,我们还是从 bound 开始跳跃,跳到串长小于等于当前前缀长度的一半的地方停下,则答案为之前递推出的值加一,注意不要弄错了,这个值不需要考虑重叠(想一想,为什么)。但是这么跳还是会超时,怎么办呢?一个显然的方法是:保证当前匹配位置不超过前缀的一半,这样就可以避免重复跳跃了。
需要注意的是,必须自增后再判断看是否需要往回跳,而不能发现自增后超过串长一半就不自增了(想一想,为什么)。唉,这么明显的错误我居然不能一眼看出来,我太弱啦!
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
putchar('\n');
}
const int mod = int(1e9) + 7;
const int maxn = int(1e6) + 5;
int n;
char str[maxn];
int f[maxn];
int g[maxn];
void solve()
{
f[0] = f[1] = 0;
g[0] = -1;
g[1] = 0;
int pre = 0, t = 0;
LL ans = 1;
for (int i = 1; i < n; i++)
{
while (pre && str[pre] != str[i]) pre = f[pre];
if (str[pre] == str[i]) pre++;
while (t && str[t] != str[i]) t = f[t];
if (str[t] == str[i]) t++;
while ((t << 1) > i + 1) t = f[t]; // note
f[i + 1] = pre;
g[i + 1] = g[pre] + 1;
ans = ans * (g[t] + 1 + 1) % mod;
}
printOut(ans);
}
void run()
{
int T = readIn();
while (T--)
{
scanf("%s", str);
n = strlen(str);
solve();
}
}
int main()
{
run();
return 0;
}
Review
看不懂?没关系,我太弱了,写出来我自己都看不懂。所以看不懂就自己去想啊!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)