提交后显示运行超时(关键词-字符串)

Question

描述

如果字符串 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;
}

这是我的代码，提交后显示运行超时，问怎么修改？

Answer 1

时间复杂度太大了，导致超时，可以用Manacher算法实现
http://t.csdn.cn/UnZ2g