用qt写一个最长回文串
时间: 2023-09-12 11:12:39 浏览: 51
以下是一个用QT编写的最长回文串程序:
```
#include <QCoreApplication>
#include <QString>
#include <QDebug>
QString longestPalindrome(QString s) {
int n = s.length();
bool dp[n][n];
int start = 0, maxLen = 1;
memset(dp, false, sizeof(dp));
for (int i = 0; i < n; i++) {
dp[i][i] = true;
for (int j = 0; j < i; j++) {
dp[j][i] = (s[j] == s[i] && (i - j < 2 || dp[j+1][i-1]));
if (dp[j][i] && i - j + 1 > maxLen) {
maxLen = i - j + 1;
start = j;
}
}
}
return s.mid(start, maxLen);
}
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
QString s = "babad";
QString result = longestPalindrome(s);
qDebug() << result;
return a.exec();
}
```
该程序使用动态规划算法,使用一个二维数组dp[i][j]表示字符串s的子串s[i...j]是否为回文串。初始化时,所有长度为1的子串都是回文串。
然后,从长度为2的子串开始,逐步计算长度更长的子串,直到计算出最长的回文串。计算过程中,如果当前子串是回文串且长度大于之前的最长回文串,则更新最长回文串的起始位置和长度。
最后,返回最长回文串即可。在上述程序中,我们使用Qt的QString类来处理字符串。