正题

---

题目大意

求长度为偶数的前缀在字符串$S$中出现的次数和。

---

解题思路

我们先不考虑长度为偶数的话，答案很好求。先求出KMP的next数组，然后$nu{m}_i=nu{m}_{nex{t}_i}+1$。
之后num的和就是答案。
注:num数组表示前i个字符的前缀等于后缀的个数

之后我们考虑长度为偶数，对于每个$num$的$+1$操作，我们发现这个$+1$是对于一个新的$i$来说的，那么改成只有$i$是偶数才加一就好了。

---

code

#include<cstdio> #include<cstring> #define N 200010 using namespace std; char s[N]; int n,next[N],j,num[N],ans; int main() {scanf("%s",s);n=strlen(s);for(int i=1;i<n;i++)//计算next{while(j&&s[i]!=s[j]) j=next[j];j+=(s[i]==s[j]);next[i+1]=j;}for(int i=1;i<=n;i++)//计算num{if(i%2==0) num[i]++,ans++;//偶数+1 get√num[i]+=num[next[i]];ans+=num[next[i]];}printf("%d",ans); }

总结

以上是生活随笔为你收集整理的nssl1217-So many prefix?【KMP】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。