精华内容
下载资源
问答
  • 最长对称子串

    2021-03-30 19:44:00
    最长对称子串 对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。 输入格式: 输入在一行中给出长度不超过1000的非空...

    最长对称子串

    对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。

    输入格式:

    输入在一行中给出长度不超过1000的非空字符串。

    输出格式:

    在一行中输出最长对称子串的长度。

    输入样例:

    Is PAT&TAP symmetric?

    输出样例:

    11

    注意字串与子序列不同
    对称字串翻转后不变,所以可以对原串与翻转后的串求最长公共子串得到答案,求最长对称序列也可同理求得

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int INF=0x3f3f3f3f;
    const ll mod=1e9+7;
    const int MAX_N=1e3+10;
    char a[MAX_N],b[MAX_N];
    int dp[MAX_N][MAX_N];
    int main(){
    	cin.getline(a,MAX_N);
    	int l=strlen(a);
    	int res;
    	for(int i=l-1;i>=0;i--) b[l-i-1]=a[i];
    	for(int i=0;i<l;i++){
    		for(int j=0;j<l;j++){
    			//a从0到i与b从0到j的最长公共子串 
    			if(a[i]==b[j]) dp[i+1][j+1]=dp[i][j]+1;
    			//更新答案 
    			res=max(res,dp[i+1][j+1]);	
    		}
    	}
    	printf("%d",res);
    	return 0;
    }
    
    展开全文
  • 对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。 输入格式: 输入在一行中给出长度不超过1000的非空字符串。 输出...

    题目要求:

    对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP
    s,于是你应该输出11。

    输入格式:

    输入在一行中给出长度不超过1000的非空字符串。

    输出格式:

    在一行中输出最长对称子串的长度。

    输入样例:

    Is PAT&TAP symmetric?

    输出样例:

    11

    这道题,并没有多难。只要仔细想一想有了思路就不难。我的想法是分为偶数和奇数。比如123321,的最长对称子串长度为6;1234321,的最长对称子串长度为7.
    有了这个思路,就靠递归,就好了。
    代码如下:

    #include<iostream>
    #include<string>
    using namespace std;
    
    int size1;
    bool Find(string str,int x,int y){//偶 
    	if(x < 0 || y > str.length()-1)return false;
    	if(str[x] == str[y]){
    		size1 += 2;
    		Find(str,x-1,y+1);
    	}else{
    		return false;
    	}
    	return true;
    }
    
    int size2 = 1;
    bool Find2(string str,int x,int y){//奇 
    	if(x < 0 || y > str.length()-1) return false;
    	if (str[x] == str[y]){
    		size2 += 2;
    		Find2(str,x-1,y+1);
    	}else{
    		return false;
    	}
    }
    
    int main(){
    	string str;
    	getline(cin,str);
    	if(str.length() == 1){
    		cout<<1<<endl;
    		return 0;
    	}
    	int max1 = -1;
    	for(int i=0;i<str.length();i++){
    		size1 = 0;
    		Find(str,i,i+1);
    		max1 = max(max1,size1);
    	}
    
    	int max2 = -1;
    	for(int i=1;i<str.length()-1;i++){
    		size2 = 1;
    		Find2(str,i-1,i+1);
    		max2 = max(max2,size2);
    	}
    	cout<<max(max1,max2)<<endl;
    	return 0;
    }
    

    我对字符串进行了两次遍历,第一次是把它的结果看作是偶数,进入Find()函数;第二次是看做奇数结果,进入Find2()函数。最后取大值。还有一点就是:只输入一个字符时,它的结果是1,这点要单独考虑。

    QwQ这几天没有什么可以让我写博客的题,要不太难太复杂,我自己都得看着别人的代码一句一句的思考。要不就是太简单,没有技术含量。ennn还是得坚持每两天更博。

    一个集坚强与自信于一身的菇凉。

    展开全文
  • 最长对称子串 最长回文子串 中心扩展法 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.StringTokenizer; public ...

    最长对称子串 最长回文子串

    对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。

    输入格式:

    输入在一行中给出长度不超过1000的非空字符串。

    输出格式:

    在一行中输出最长对称子串的长度。

    输入样例:

    Is PAT&TAP symmetric?

    输出样例:

    11

    j解法1:中心扩展,确定中心点,然后向两边扩展搜索

    import java.util.Scanner;
    
    public class Main {
    	static StringBuilder Writer = new StringBuilder();
    	static Scanner Reader = new Scanner(System.in);
    
    	public static void main(String[] args) throws IOException {
    		slove();
    		System.out.print(Writer);
    	}
    
    	// 解答入口
    	static void slove() throws IOException {
    		String str = Reader.nextLine();
    		char[] chs = str.toCharArray();
    		int length = str.length();
    		
    		int LEFT = (length - 1) / 2; // 中心点的左边
    		int RIGHT = length / 2; // 中心点的右边
    		int step = 0; // 左右横跳的步长
    		int max = 1; // 记录最大长度
    		
    		while (step < LEFT) {
    			if ((LEFT - step + 1) * 2  <= max) {
    				break; // 如果当前长度比接下来的最大长度都要长,则不必继续下去
    			}
    			// 循环2次,一次向左边,一次向右边(通过控制step的正负实现)
    			int n = 2;
    			while (n-- > 0) {
    				// 确定中心点
    				int left = LEFT + step;
    				int right = RIGHT + step;
    				// 取较大值
    				int len = fun(chs, left, right);
    				max = max < len ? len : max;
    				
    				// setp小于0,向左边搜索
    				// setp大于0,向右边搜索
    				// seto等于0,第一次搜索
    				if (step < 0) {
    					left = LEFT + step;
    					right = RIGHT + step - 1;
    				} else if (step == 0) {
    					if (left != right) {
    						left = LEFT + step;
    						right = RIGHT + step - 1;
    						len = fun(chs, left, right);
    						max = max < len ? len : max;
    						left = LEFT + step + 1;
    						right = RIGHT + step;
    						len = fun(chs, left, right);
    						max = max < len ? len : max;
    					}
    					break;
    				} else {
    					left = LEFT + step + 1;
    					right = RIGHT + step;
    				}
    				len = fun(chs, left, right);
    				max = max < len ? len : max;
    
    				step = -step;
    			}
    			step++;
    		}
    		Writer.append(max);
    	}
    	
    	// 根据给定的中心点向两边搜索,返回当前中心点的最大长度
    	static int fun(char[] chs, int left, int right) {
    		while (!(left < 0 || right >= chs.length)) {
    			if (chs[left] != chs[right]) {
    				break;
    			}
    			left--;
    			right++;
    		}
    		return right - left - 1;
    
    	}
    
    }
    

    解法2:动态规划,由某个字符串是对称的,那么它的子串也是对称的这个规律来进行递推
    表格填写规则:
    规则1:如果 str[s] = str[e] && (e - s) < 2,则map[s][e] = 1
    规则2:如果 str[s] = str[e] && map[s-1][e+1] = 1,则map[s][e] = 1
    规则1说的是回文字符串的长度是1和2的情况
    规则2的意思是该字符串(下标从 s 到 e这个字符串)的 开头和结尾是一样的( str[s] = str[e]) ,那么就去看它的子字符串是不是回(map[s-1][e+1] = 1),是回文,则该字符串也是回文。

    画出表格
    在这里插入图片描述
    由表格可以看出,最长的回文序列是从下标1开始到下标为11的位置(闭区间),总共长度是11

    import java.util.Scanner;
     
    public class Main{
     
    	/*
    	 * 最长回文子串(动态规划解决方法)
    	 * 思路:pal数组标记位于j~i之间串是否为回文子串
    	 * 若判断j~i间是否为回文子串,需依赖于 j+1 ~ i-1间子串类型,依此类推
    	 * 直到依赖项为x或者xy,(x,y未知)(仔细体会为什么是这样)
    	 * i-j<2 :用于判断x或者xy的情况,当然不要忽略&&的短路效应
    	 */
    	public static int longestPalindrome(String str){
    		int n=str.length();
    		boolean[][] pal=new boolean[n][n];
    		int maxLen=0;
    		for(int i=0;i<n;i++){
    			for(int j=i;j>=0;j--){ 
    				if(str.charAt(i)==str.charAt(j) && (i-j<2 || pal[j+1][i-1]==true)){
    					pal[j][i]=true;
    					maxLen=Math.max(maxLen, i-j+1);
    				}
    			}
    		}
    		return maxLen;
    	}
     
    	public static void main(String[] args) {
    		// Is PAT&TAP symmetric?     
    		//result:11
    		Scanner in = new Scanner(System.in);
    		String str = in.nextLine();
    		System.out.println(longestPalindrome(str));
    	}
    }
    

    解法2是另外一位博主的解法,记录一下、
    博文链接:https://blog.csdn.net/SJshenjian/article/details/61616221

    展开全文
  • 题目链接:https://www.patest.cn/contests/gplt/L2-008L2-008. 最长对称子串题目描述:对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定”Is PAT&TAP symmetric?”,最长对称子串为”s PAT&TAP s”,...

    题目链接:https://www.patest.cn/contests/gplt/L2-008

    L2-008. 最长对称子串

    题目描述:

    对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定”Is PAT&TAP symmetric?”,最长对称子串为”s PAT&TAP s”,于是你应该输出11。

    输入格式:

    输入在一行中给出长度不超过1000的非空字符串。

    输出格式:

    在一行中输出最长对称子串的长度。

    输入样例:

    Is PAT&TAP symmetric?

    输出样例:

    11

    参考资料:

    【动态规划】最长公共子序列与最长公共子串

    AC代码:

    #include<bits/stdc++.h>
    
    using namespace std;
    
    int lcs(string s1,string s2){
        int len1 = s1.length();
        int len2 = s2.length();
    
        int ans  = 0;
        int **c = new int*[len1+1];
        for(int i = 0;i < len1+1;i++){
            c[i] = new int[len2+1];
        } 
    
        for(int i = 0; i < len1+1; i++)
            c[i][0]=0;        //第0列都初始化为0
        for(int j = 0; j < len2+1; j++)
            c[0][j]=0;        //第0行都初始化为0 
    
        for(int i = 1;i <= len1;i++){
            for(int j = 1;j <= len2;j++){
                 if(s1[i-1] == s2[j-1]){
                    c[i][j] = c[i-1][j-1] + 1;
                    ans = max(ans,c[i][j]); 
                }else{
                    c[i][j] = 0;
                }
            }
        }
        return ans;
    }
    
    int main(){
    
    //  freopen("a.txt","r",stdin);
        char s1[1001];
        char s2[1001];
        while(gets(s1)){
            string a = s1;
            int  j = 0;
            for(int i = strlen(s1)-1;i >= 0;i--){
                s2[j] = s1[i];
                j++;
            }
            string b = s2;
            cout << lcs(a,b) << endl; 
        }
        return 0;
    }
    
    展开全文
  • 7-6 最长对称子串 (25分) 对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。 输入格式: 输入在一行中给出长度不超过1000的...
  • 最长对称子串 时间限制 100 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越 对给定的字符串,本题要求你输出最长对称子串的长度。例如,...
  • PTA——最长对称子串

    2020-01-26 19:41:35
    PTA——最长对称子串 对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。 输入格式: 输入在一行中给出长度不超过1000的...
  • 7-5 最长对称子串

    2020-12-27 14:20:56
    7-5 最长对称子串 (25分) 对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。 输入格式: 输入在一行中给出长度不超过...
  • PTA-最长对称子串

    2020-08-19 10:08:19
    对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。 输入格式: 输入在一行中给出长度不超过1000的非空字符串。 输出格式: 在...
  • PAT最长对称子串

    2017-03-24 17:13:55
    最长对称子串 时间限制 100 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越 对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定"Is PAT&TAP ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,092
精华内容 436
关键字:

最长对称子串