主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
题解：P11276 第一首歌
最后更新于 2025-06-15 15:22:48
作者
Laisira
分类
题解
题解
P11276
复制 Markdown
查看原文
更新内容
### 思路 显然答案就是最长的区间 $[1,r]$，使得从 $1$ 到 $r$ 的串等于从 $n-r+1$ 到 $n$ 的串，就是 KMP 中的 $n-nxt_n$。 ### 代码 ```cpp #include<bits/stdc++.h> #define Maxn 1000005 using namespace std; int nxt2[Maxn]; void KMP(int n,string s,int *nxt) { int j = 0; for(int i=2;i<=n;i++) { while(j&&s[j+1] != s[i]) j = nxt[j]; if(s[j+1] == s[i])j++; nxt[i] = j; } } int main() { string t; cin>>t; int m = t.size(); t = ' '+t; KMP(m,t,nxt2); int p = m-nxt2[m]; // cout<<m-p<<" "; for(int i=1;i<=p;i++) cout<<t[i]; for(int i=1;i<=m;i++) cout<<t[i]; return 0; } ```
正在渲染内容...
点赞
0
收藏
0
