描述
如果字符串 S 是字符串 T 的一部分, 那么我们就称 S 是 T 的一个子串
例如
"abc", "bcd", "de" 都是"abcde"的子串.
当然, 字符串 T 本身也是 T 的子串.
如果字符串 S 是一个回文串, 同时又是字符串 T 的一个子串,
那么我们就称 S 是 T 的回文子串 .
输入
每组数据一个字符串, 只包含小写字母,并且字符串长度不超过10000.
输出
请输出字符串的最长回文子串的长度.
输入样例 1
abcde
输出样例 1
1
输入样例 2
cabba
输出样例 2
4
#include<bits/stdc++.h>
using namespace std;
int dp[10000][10000];
int main() {
string s1;
int ans=1;
while(getline(cin,s1)) {
int n=s1.size();
for(int i=0; i<n; i++) {
dp[i][i]=1;
if(i<n-1) {
if(s1[i]==s1[i+1]) {
dp[i][i+1]=1;
ans=2;
}
}
}
for(int L=3; L<=n; L++) {
for(int i=0; i+L-1<n; i++) {
int j=i+L-1;
if(s1[i]==s1[j]&&dp[i+1][j-1]==1) {
dp[i][j]=1;
ans=L;
}
}
}
cout << ans << endl ;
}
return 0;
}
这是我的代码,提交后显示运行超时,问怎么修改?