密码截取

/*
    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));
        }
    }
}

#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;
}

// 最长回文子串
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;
    }
}

# 改版
def zcHW(s):
    if s == s[::-1]:
        return len(s)
    s = list(s)
    newS = '#' + '#'.join(s) + '#'
    Len = len(newS)
    maxLen = [1] * Len # 默认自身为回文
    for i in range(1,Len):
        # 对于索引i，前面有i个元素，索引为[0:i]，后面有Len-i-1个元素，索引[i+1:Len]
        r = min(i, Len-i-1) # 能够达到的最大半径r
        m = 1 # 假设的初始半径
        while m <= r:
            # 当前元素以半径为准，对左右两侧的元素逐一比对
            if newS[i-m] == newS[i+m]:
                maxLen[i] = m 
                m += 1
            else: # 如果不相等了，跳出while循环，去判断下一个i
                break
    return maxLen

while True:
    try:
        s = input().strip()
        maxLen = zcHW(s)
        print(max(maxLen))
    except:
        break

while True:
    try:
        num = input()
        n = len(num)
        count = 0
        while n >= 1:
            for i in range(len(num)-n+1):
                if num[i:i+n] == num[i:i+n][::-1]:
                    print(n)
                    count += 1
                    break
            if count == 1:
                break
            else: n -= 1
    except:
        break