密码截取

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int Manacher(string oriStr) {
	string newStr;
	int len = oriStr.size();
	for (int i = 0; i < len; i++) {//插入间隔符
		newStr += '#';
		newStr += oriStr[i];
	}
	newStr += '#';
	len = 2 * len + 1;             //新串长度，必为奇数
	int maxRight = 0;              //当前访问到的所有回文子串中，所能触及的最右一个字符的位置
	int pos = 0;                   //maxRight对应的回文子串对称轴的位置
	int*RL = new int[len];         //RL[i]记录以i为对称轴的最长回文子串半径长度（对称轴到最左或最右的距离）
	int maxLength = 0;             //记录最长回文子串长度
	for (int i = 0; i < len; i++) {
		if (i < maxRight) {        //分两种情况，i在maxRight左边和右边
			RL[i] = min(RL[2 * pos - i], maxRight - i);
		}
		else RL[i] = 1;
		while (i - RL[i]>=0 && RL[i] + i < len && newStr[i - RL[i]] == newStr[i + RL[i]])
			RL[i]++;               //以i为中心，在上步的基础上扩展，直至到达边界或左右字符不相等
		if (maxRight < RL[i] + i - 1) {//更新maxRight和pos
			maxRight = RL[i] + i - 1;
			pos = i;
		}
		maxLength = max(maxLength, RL[i] - 1);//对以i为中心的回文子串在原串总的长度即为RL[i] - 1
											  //证明：新串中回文子串长度为2*RL[i]-1，其中RL[i]个
											  //插入字符，则剩下的RL[i]-1个为原字符
	}
	return maxLength;
}

int main() {
	string str;
	while (cin >> str) {
		cout << Manacher(str) << endl;
	}
	return 0;
}

用了一个比较笨的方法，对于每一个字符，看他是不是与下一个字符相等（BAAB型），或者看他的上一个字符与下一个字符是否相等（ABA型），然后往回找就可以了
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
    string str;
    while(getline(cin,str)){
        int len = str.length();
        if(len<=1)
        {
            cout<<len<<endl;
            continue;
        }
        int num = 1;
        for(int i=1;i<len-1;i++)
        {
            if(str[i]==str[i+1])
            {//偶数对成
                int curnum = 0;
                int start = i;int end =i+1;
                while(start>=0 && end<=len && str[start] == str[end])
                {
                    start--;
                    end++;
                    curnum+=2;
                }
                if(curnum>num)
                    num = curnum;
            }
            if(str[i-1]==str[i+1])
            {//偶数对成
                int curnum = 1;
                int start = i-1;int end =i+1;
                while(start>=0 && end<=len && str[start] == str[end])
                {
                    start--;
                    end++;
                    curnum+=2;
                }
                if(curnum>num)
                    num = curnum;
            }
        }
        cout<<num<<endl;
    }
    return 0;
}

#include<iostream>
#include<vector>
using namespace std;
int main(){
	string str;
    while(cin >> str){
        vector<int> vi;       
        int len = str.size();
        for(int i = 0; i < len-1; ++i){
            for(int j = len-1; j > i; --j){
				if(str[i] == str[j]){
                    int i1 = i, j1 = j;
                    while(str[i1] == str[j1]){
                        if(i1 == j1-1 || i1 == j1)
                             vi.push_back(j-i+1);
                        i1++;
                        j1--;
                    } 
                }
            }
        }
        int max = vi[0];
        for(int i = 1; i < vi.size(); ++i){
           if(vi[i] > max)
               max = vi[i];
        }
        cout << max << endl;
    }
    return 0;
}

while True:
    try:
        s=list(input())
        count=0
        if len(s)==2:
            if s[0]==s[1]:
                print(2)
            else:
                print(0)
        else:
            for i in range(1,len(s)-1):
                if s[i]==s[i+1]:
                    num=0#偶数成对
                    start=i
                    end=i+1
                    while start>=0 and end<=(len(s)-1) and s[start]==s[end]:
                            start-=1
                            end+=1
                            num+=2
                    if num>count:
                        count=num
                if s[i-1]==s[i+1]:
                    num=1#奇数成对
                    start=i-1
                    end=i+1
                    while start>=0 and end<=(len(s)-1) and s[start]==s[end]:
                        start-=1
                        end+=1
                        num=num+2
                    if num>count:
                        count=num
            print(count)
    except:
        break

/*
    https://ethsonliu.com/2018/04/manacher.html
    https://leetcode.wang/leetCode-5-Longest-Palindromic-Substring.html#

    左程云算法讲解视频
    https://www.bilibili.com/video/BV13g41157hK?p=13
    位置1:30分
 */
import java.util.Scanner;

public class Main {

    // 字符串预处理
    public static char[] manacherString(String str) {
        char[] chars = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;

        for (int i = 0; i < res.length; i++) {
            if (i % 2 == 0) {
                res[i] = '#';
            } else {
                res[i] = chars[index];
                index++;
            }
        }
        return res;
    }

    public static int manacher2(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] s = manacherString(str);
        int[] p = new int[s.length];
        int C = 0;
        int R = 0;
        int maxLen = Integer.MIN_VALUE;

        for (int i = 0; i < s.length; i++) {
            int iMirror = 2 * C - i;
            if (i < R) {
                p[i] = Math.min(p[iMirror], R - i);
            } else {
                p[i] = 1;
            }
            while (i + p[i] < s.length && i - p[i] >= 0) {
                if (s[i + p[i]] == s[i - p[i]]) {
                    p[i]++;
                } else {
                    break;
                }
            }
            if (i + p[i] > R) {
                R = i + p[i];
                C = i;
            }
            maxLen = Math.max(maxLen, p[i]);
        }
        return  maxLen - 1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String str = sc.nextLine();
            System.out.println(manacher2(str));
        }
    }
}

def longestPalindrome(s):
    if s == s[::-1]: return len(s)
    maxLen = 0
    for i in range(len(s)):
        #如果结果为奇数
        if i - maxLen >= 1 and s[i - maxLen - 1:i + 1] == s[i - maxLen - 1:i + 1][::-1]:
            maxLen += 2
        (3534)#如果结果为偶数
        elif i - maxLen >= 0 and s[i - maxLen:i + 1] == s[i - maxLen:i + 1][::-1]:
            maxLen += 1
    return maxLen
while True:
    try:
        a = input()
        if a:
            print(longestPalindrome(a))

    except:
        break

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
    string str;
    while (getline(cin, str)) {
        int max = 1;
        for (int i = 0; i < str.size(); i++) {
            int count = 0;
            for (int left = i - 1, right = i + 1; left >= 0 && right < str.size(); left--, right++) {
                if (str[left] == str[right]) {
                    count++;
                    if (max < (2 * count + 1)) max = 2 * count + 1;
                }
                else break;
            }
        }
        for (int i = 0; i < str.size() - 1; i++) {
            int count = 0;
            for (int left = i, right = i + 1; left >= 0 && right < str.size(); left--, right++) {
                if (str[left] == str[right]) {
                    count++;
                    if (max < (2 * count)) max = 2 * count;
                }
                else break;
            }
        }
        cout << max << endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <cctype>
#include <string.h>

using namespace std;

int main()
{
    string str;
    while(cin>>str)
    {
        int len = str.size();
        vector< vector< bool>> f( len, vector< bool >( len ) );
        int maxlen = 1;//返回子串的起点和长度

        for( int i = 0 ; i < len ; i++ )
        {
            f[ i ][ i ] = 1;
            for( int j = 0 ; j < i ; j++ )//[j,i]
            {
                f[ j ][ i ] = ( str[ j ] == str[ i ] &&
                                ( i == j + 1 || f[ j + 1 ][ i - 1 ] ) );//注意此处的理解
                if( f[ j ][ i ] && i - j + 1 > maxlen )
                {
                    maxlen = i - j + 1;
                }
            }
        }
        
        cout<<maxlen<<endl;
        
    }
    return 0;
}

// 最长回文子串
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            String st=sc.next();
            int maxLen=0;
            for(int i=1;i<st.length()-1;i++){
                int j=0;
                for(j=1;i-j>=0 && i+j<st.length();j++){
                    if(st.charAt(i-j)!=st.charAt(i+j))
                        break;
                }
                maxLen=Math.max(maxLen,2*j-1);
                if(st.charAt(i)==st.charAt(i+1)){
                    for(j=1;i-j>=0 && i+1+j<st.length();j++){
                        if(st.charAt(i-j)!=st.charAt(i+1+j))
                            break;
                    }
                    maxLen=Math.max(maxLen,2*j);
                }
            }
            System.out.println(maxLen);
        }
    }
}

//同楼上一位答主一样，以每个字符（奇数长度的回文串）或者字符间空隙
//（偶数长度的回文串）分别向左向右扩充，记录遇到的最大长度
import java.util.Scanner;


public class Main{
	public static int process(String str){
		int len=str.length();
		if(len<1){
			return 0;
		}
		int max=1;//只要字符创长度大于1，则最短的回文串长度为1
		//考虑奇数个数的回文串
		for(int i=1;i<len-1;i++){
			int k=i-1,j=i+1;
			int count=0;
			while(k>=0 && j<=len-1){
				if(str.charAt(k--)==str.charAt(j++)){
					count++;
				}else{
					break;
				}
			}
			max= (max>=(count*2+1)) ? max:(count*2+1);
		}
		//现在考虑偶数回文串的情况，主要考虑字符之间的位置
		for(int i=1;i<len-1;i++){
			int k=i-1,j=i;
			int count=0;
			while(k>=0 && j<=len-1){
				if(str.charAt(k--)==str.charAt(j++)){
					count++;
				}else{
					break;
				}
			}
			max= (max>=count*2) ? max : (count*2);
		}
		return max;
	}
	public static void main(String[] args){
		Scanner in=new Scanner(System.in);
		while(in.hasNext()){
			String str=in.next();
			System.out.println(process(str));
		}
		in.close();
	}
}

s = input()
n = len(s)
dp = [[0 for _ in range(n)]for _ in range(n)]
dp[n-1][n-1]=1
for i in range(n-1):
    dp[i][i]=1
    dp[i][i+1] = 2 if s[i]==s[i+1] else 1
for L in range(n-3,-1,-1):
    for R in range(L+2,n):
        temp = s[L:R+1]
        dp[L][R] = max(dp[L+1][R],dp[L][R-1])
        if temp==temp[::-1]:
            dp[L][R]=max(dp[L][R],len(temp))
print(dp[0][n-1])

import java.util.Scanner;

public class Main{
    public static int lenRoundStr(String s, int left, int right){
        while(left>=0 && right<s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return right - left - 1;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String pw = sc.nextLine();
        int maxValue = Integer.MIN_VALUE;
        for(int i=0; i<pw.length()-1; i++){
            int ans = Math.max(lenRoundStr(pw, i, i), lenRoundStr(pw, i, i+1));
            maxValue = Math.max(ans, maxValue);
        }
        maxValue = Math.max(lenRoundStr(pw, pw.length()-1, pw.length()-1), maxValue);
        System.out.println(maxValue);
    }
}

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
    string s;
    while(cin>>s){
        int n=s.size();
        //求最长回文子串
        vector<vector<bool>> dp(n,vector<bool>(n,false));
        for(int i=0;i<n;i++){
            dp[i][i]=true;
        }
        int ans=0;
        for(int i=n-2;i>=0;i--){
            for(int j=i+1;j<n;j++){
                if(s[i]==s[j]){
                    if(j-i>2){
                        if(dp[i+1][j-1]){
                            dp[i][j]=true;
                            ans=max(ans,j-i+1);
                        }
                    }else{
                        dp[i][j]=true;
                        ans=max(ans,j-i+1);
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

//中心扩散算法
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String s = sc.nextLine();
            int ans = maxLen(s);
            System.out.println(ans);
        }
    }
    
    private static int maxLen(String s){
        if(s==null || s.length()==0) return 0;
        if(s.length()==1) return 1;
        
        int max = 0;
        int len = s.length();
        for(int i=0; i<s.length(); i++){
            int cur = 1;
            int left=i-1, right=i+1;
            while(left>=0 && s.charAt(left)==s.charAt(i)){//左边相同移动
                left--;
                cur++;
            }
            while(right<len && s.charAt(right)==s.charAt(i)){//右边相同移动
                right++;
                cur++;
            }
            while(left>=0 && right<len && s.charAt(left)==s.charAt(right)){//两边同时相同移动
                left--;
                right++;
                cur += 2;
            }
            if(cur>max) max = cur;
        }
        return max;
    }
}