【2019HDU多校】扩展kmp模板题
传送门
扩展KMP模板题
要你求对于每个后缀,与前缀匹配的最大长度
是我太菜了,居然不知道有这个算法。。。。。被签到题自闭十万年
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 233;
typedef long long ll;
bool vis[maxn];
char a[maxn], b[maxn];
int nxt[maxn], f[maxn];
int main()
{
int T; cin >> T;
while(T--)
{
scanf("%s" , a);
int n = strlen(a);
memset(nxt, 0, sizeof nxt);
nxt[0] = n;
int j = 0;
while(j + 1 < n && a[j] == a[j + 1]) j++;
nxt[1] = j;
int p0 = 1;
for(int i = 2; i < n; i++)
{
if(i + nxt[i - p0] < nxt[p0] + p0) nxt[i] = nxt[i - p0];
else
{
j = max(0, nxt[p0] + p0 - i);
while(a[j] == a[i + j] && i + j < n) j++;
nxt[i] = j;
p0 = i;
}
}
ll ans = 0;
for(int i = 1; i < n; i++)
{
if(nxt[i] == n - i) ans += nxt[i];
else ans += nxt[i] + 1;
}
printf("%lld\n", ans);
}
}
发表评论