PAT 1040 Longest Symmetric String[dp][难]

时间:2022-04-21 04:08:08
1040 Longest Symmetric String (25)(25 分)

Given a string, you are supposed to output the length of the longest symmetric sub-string. For example, given "Is PAT&TAP symmetric?", the longest symmetric sub-string is "s PAT&TAP s", hence you must output 11.

Input Specification:

Each input file contains one test case which gives a non-empty string of length no more than 1000.

Output Specification:

For each test case, simply print the maximum length in a line.

Sample Input:

Is PAT&TAP symmetric?

Sample Output:

11

题目大意:

//自己写的土鳖方法,以每个字符串为对称中心进行判断。一开始只考虑了对称长度是偶数的情况,没有考虑奇数。得了21分。加上判断奇数的,只得了23分,还是有一个测试点没过去,没找到是什么原因,暂时放一下。

#include <iostream>
#include <algorithm>
#include <string>
#include<stdio.h>
using namespace std; int main() {
string s="";
char ch;
while(ch=getchar()){
if(ch=='\n')break;
if(ch==' ')s+=" ";
else s+=ch;
}
int len=s.size();
int ct=,tp=;
for(int i=;i<len-;i++){
for(int j=;j<=i;j++){
if(i+j>=len)break;
if(s[i-j]==s[i+j])
tp++;
else break;
}
if(*tp+>ct)ct=*tp+;
tp=;
}
tp=;
for(int i=;i<len-;i++){
for(int j=;j<=i;j++){
if(i+j+>=len)break;
if(s[i-j]==s[i+j+])
tp++;
else break;
}
if(*tp>ct)ct=*tp;
tp=;
}
cout<<ct;
return ;
}

这个代码也是通过判断对阵中心,不过使用了reverse函数, 以前见过的,对string判断对称,使用reverse

通过截取,如果是偶数时,那么对称中心就是中间靠左的那个,(和中位数一样。)

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
string s;
getline(cin, s);
int len = ;
for (int i = ; i < s.size(); i++){
for (int j = ; j <= min(i, int(s.size())--i); j++){
//这个最小值表示向左向右还最多可以截取几个。是需要min来限制的。
string s2 = s.substr(i-j,*j+);
string s3 = s2;
reverse(s2.begin(), s2.end());
if (s2 == s3){
if (s2.size() > len)
len = s2.size();
}
string s4 = s.substr(i-j, *j+);//这个如果i指向,最后一个,是会和上边重判的。是截取一个。
string s5 = s4;
reverse(s4.begin(), s4.end());
if (s4 == s5){
if (s4.size() > len)
len = s4.size();
}
}
}
printf("%d\n", len);
return ;
}

//下面是大佬的dp版本:https://www.liuchuo.net/archives/2104

#include <iostream>
#include<stdio.h>
using namespace std;
int dp[][];//dp[i][j]只有0和1取值,表示i和j之间是否是
int main() {
string s;
getline(cin, s);//直接getline可以读进去字符串里。
int len = s.length(), ans = ;
for(int i = ; i < len; i++) {
dp[i][i] = ;
if(i < len - && s[i] == s[i+]) {
dp[i][i+] = ;
ans = ;
}
}
for(int L = ; L <= len; L++) {
for(int i = ; i + L - < len; i++) {//总长度的限制。
int j = i + L -;
if(s[i] == s[j] && dp[i+][j-] == ) {
dp[i][j] = ;
ans = L;
}
}
}
printf("%d", ans);
return ;
}

//dp数据只有0和1取值,dp[i][j]表示i到j是否是对称的,为了保证状态的转移,使用长度作为循环,因为2很好判断,那么就从L=3开始,i每次都从0开始,那么j就是那个对应的结束,要满足的条件自然是j+L-1<len了。而最终的答案自然是最大的L。还有dp[i+1][j-1]也是神了,这就是坐进右退判断对称的。