好高興，為數(shù)不多的我沒看題解的題·，我用的是O(n)時間求回文串長度的算法算法在我上一篇博客。

然后就是注意細節(jié)了。

/*
ID:jinbo wu
TASK: calfflac
LANG:C++
*/
#include<bits/stdc++.h>
using namespace std;
struct node
{char c;int n;
}a[40010];
string s;
int p[40020];
int main()
{freopen("calfflac.in","r",stdin);freopen("calfflac.out","w",stdout);string str="";while(getline(cin,str)){s+='\n';s+=str;}int l=s.length();a[0].c='$';a[1].c='#';int len=2;int ans=0,m=0;for(int i=0;i<l;i++){if(s[i]>='a'&&s[i]<='z'){a[len].c=s[i];a[len++].n=i;a[len++].c='#';}else if(s[i]>='A'&&s[i]<='Z'){a[len].c=s[i]-'A'+'a';a[len++].n=i;a[len++].c='#';}}int id=0,mx=0;for(int i=0;i<len;i++){if(mx>i)p[i]=min(mx-i,p[2*id-i]);else p[i]=1;while(a[i-p[i]].c==a[i+p[i]].c)p[i]++;if(i+p[i]>mx){mx=i+p[i];id=i;}if(ans<p[i]){ans=p[i];m=i;}}int ss,e,cnt=0;e=a[m+p[m]-2].n;ss=a[m-p[m]+2].n;cout<<ans-1<<endl;for(int i=ss;i<=e;i++){if(s[i]=='\n')cout<<endl;elsecout<<s[i];}cout<<endl;
}

這題數(shù)據(jù)不大所以只比別的代碼快一點
Executing...
? ?Test 1: TEST OK [0.000 secs, 4652 KB]
? ?Test 2: TEST OK [0.000 secs, 4652 KB]
? ?Test 3: TEST OK [0.000 secs, 4652 KB]
? ?Test 4: TEST OK [0.000 secs, 4652 KB]
? ?Test 5: TEST OK [0.000 secs, 4652 KB]
? ?Test 6: TEST OK [0.000 secs, 4652 KB]
? ?Test 7: TEST OK [0.000 secs, 4652 KB]
? ?Test 8: TEST OK [0.000 secs, 4652 KB]

總結(jié)

以上是生活随笔為你收集整理的usaco Calf Flac(O(n)时间求回文串长度）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。