最长回文子串

#include <bits/stdc++.h>
using namespace std;
  int longestPalindrome(string s) {
        int left = 0,right = 0,len = 0;
          int n=s.size();
      vector<vector<int> > dp(n,vector<int>(n,0));
        for(int i=0;i<s.size();i++)
        {
             dp[i][i]=1;
            for(int j=0;j<i;j++)
            {
                dp[j][i] = (s[i]==s[j] &&(i-j<2 || dp[j+1][i-1]));
                if(dp[j][i] && len<i-j+1)
                {
                    len = i-j+1;
                    left=j;
                    right=i;
                }                
            }
        }
        int res=right-left+1;
        return res;       
    } 
int main()
{
    string s;
    while(cin>>s)
    {
        int res=0;
        res=longestPalindrome(s);
        cout<<res<<endl;
    }
    
}

import java.util.Scanner;
public class Main {

    public static int maxLongHuiwen(String str) {
        //等价于求str字符串的逆序字符串和str的最长公共子串，动态
        String strrev = new StringBuilder(str).reverse().toString();
        int len = str.length();
        int[][] dp = new int[len + 1][len + 1];
        int max = 0; //记录最长公共子串的长度
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= len; j++) {
                if (str.charAt(i - 1) == strrev.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = 0;
                if (dp[i][j] > max) {
                    max = dp[i][j];
                }
            }
        }
        return max;
    }

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

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
string findLongestPalindromeManacher(const string s){
    string s1("^#");
    for (auto ch : s){
        s1 += ch;
        s1 += '#';
    }
    s1 += '$';
    vector<int>pv(s1.length(), 0);//记录回文半径
    int index(0), mlen(1);
    for (int k1 = 2, mid = 1, mxr = 0; k1 < s1.length(); ++k1){
        pv[k1] = k1 < mxr ? min(pv[mid * 2 - k1], mxr - k1) : 1;
        while (s1[k1 + pv[k1]] == s1[k1 - pv[k1]]){
            ++pv[k1];//回文半径增加
        }
        if (mxr < mid + pv[k1]){
            mxr = mid + pv[k1];
            mid = k1;
        }
        if (mlen < pv[k1]){
            mlen = pv[k1];
            index = k1;
        }
    }
    return s.substr((index - mlen) / 2, mlen - 1);
}
int main(){
    string s;
    while (cin>>s)
    {
        string s1 = findLongestPalindromeManacher(s);
        cout << s1.length() << endl;
    }
    return 0;
}

int main(){
    string str;
    while(cin >> str)
    {
        vector<vector<int>>dp(str.size(), vector<int>(str.size()));
        int ans = 1;
        for(int i = 0; i < str.size(); ++i)
        {
            dp[i][i] = 1;
            if(i < str.size() - 1)
            {
                if(str[i] == str[i+1])
                {
                    dp[i][i+1] = 1;
                    ans = 2;
                }
            }
        }
        
        for(int L = 3; L <= str.size(); ++L)
            for(int i = 0; i + L - 1 < str.size(); ++i)
            {
                int j = i + L -1;
                if(str[i] == str[j] && dp[i+1][j-1])
                {
                    dp[i][j] = 1;
                    ans = L;
                }
            }
        cout << ans << endl;
    }
}

  function toManacherString(str) {
    let a = ['#'];
    for (let i=0;i<str.length;i++) {
      a.push(str[i]);
      a.push('#');
    }
    return a;
  }

  function manacher(str) {
    let a = toManacherString(str);
    let ra = Array(a.length).fill(0);
    let c = -1, r = -1;
    let max = Number.MIN_SAFE_INTEGER;
    debugger;
    for (let i = 0; i < a.length; i++) {
      if (r > i) {
        let pl = 2 * c - i;
        if (pl - ra[pl] > c - r) {
          ra[i] = ra[pl];
          continue;
        } else if (pl - ra[pl] < c - r) {
          ra[i] = r - i + 1;
          continue;
        } else {
          ra[i] = r - i + 1;
        }
      }
      while (i + ra[i] < ra.length && i - ra[i] > -1) {
        if (a[i + ra[i]] === a[i - ra[i]]) {
          ra[i]++;
        } else {
          break;
        }
      }
      if (i + ra[i] > r) {
        r = i + ra[i] - 1;
        c = i;
      }
      if (ra[i] > max) {
        max = ra[i];
      }
    }
    return max - 1;
  }
let input =readline();
print(manacher(input))

def longestPalindrome( s: str) -> str:
    if not s:
        return ""
    n = len(s)
    res=[]
    for i in range(1, n):
        # 中轴情况
        j = 1
        while i - j >= 0 and i + j <= n-1 and s[i - j] == s[i + j]:
            j += 1
        j-=1
        num=j*2+1
        res.append(num)
        # 对称情况
        j = 1
        while i - j >=0 and i + j - 1 <= n-1 and s[i - j] == s[i + j - 1]:
            j += 1
        j-=1
        num=j*2
        res.append(num)
    num=max(res)
    return num
while True:
    try:
        s=input()
        print(longestPalindrome(s))
    except:
        break

//N为字符串长度，i为定位器，其作用是寻找最长回文子串的中心，left和right
//是从i左端（或自身）和右段延申出去的定位器，最终是最长回文字串左端减一和右端加一的位置。可以看到我把代码复制了两次，其中的不同就在于
//for循环中的left=i和left=i-1，这是因为最长回文字串有可能是偶数或者奇数个，此时i可能是X.5，或者X，（X为最长回文子串中心的位置）
//此外，本题如果出现了段越界，就是你先前定义的数组不够大的原因，一开始我定义了100个都不够用
#include <stdio.h>
#include <string.h>
int main( )
{
    char a[1000];
    int N=0,i=1,left,right,lenth;
    while(scanf("%s",a)!=EOF){
        //printf("%s",a);
        
    N=strlen(a);lenth=0;
        for(i=0;i<N;i++)
        {left=i,right=i+1;
    while(left>=0&&right<N&&a[left]==a[right])
    {
     left--;
     right++;
    }
    if(right-left-1>lenth)
    {
        lenth=right-left-1;
    }
        }
    for(i=0;i<N;i++)
        {left=i-1,right=i+1;
    while(left>=0&&right<N&&a[left]==a[right])
    {
     left--;
     right++;
    }
    if(right-left-1>lenth)
    {
        lenth=right-left-1;
    }
        }
printf("%d\n",lenth);
   }
        return 0;
}

#include <iostream>
using namespace std;

int main() 
{
	
	string str;

	while ( cin >> str )
	{
		int len = str.size();
		bool dp[len][len];//字符串i到j区间是否为回文子串

		for (int i=0;i<len;i++)
		{
			for (int j=0;j<len;j++)
			{
				dp[i][j] = false;
			}
		}

		for (int i=0;i<len;i++)
		{
			dp[i][i] = true;
		}

		int imax=0;
		for (int j=1;j<len;j++)
		{
			for (int i=0;i<=j;i++)		
			{
				if (str[i] == str[j])
				{
					if (j-i<3)
					{
						dp[i][j] = true;
					}
					else
					{
						dp[i][j] = dp[i+1][j-1];
					}

					if (dp[i][j])
					{
						imax = imax > (j-i+1) ? imax : (j-i+1);
					}
				}
			}
		}

		cout << imax <<endl;

	}
	return 0;
}

#include<stdio.h>
#include<string.h>
#define N 1024
 int main()
 {   char str[N];
  while (scanf("%s",str)!=EOF){
      int n= strlen(str);
      int i,k,sum,max;
      max=0;
      for (i=0;i<n;i++)
      {   sum=0;
          if(str[i]==str[i+1]) 
          { for(k=0;k<n;k++)
            {if(str[i-k]==str[i+k+1]) { sum=sum+1;  }
             else if(str[i-k]!=str[i+k]) break;}
          }
          if (max<sum) max=sum;
      }
      printf("%d",max*2);
 } return 0;
 }

#include <stdio.h>

int main(void)
{
    char string[1000];
    int idx = 0;
    int right = 0;
    int left = 0;
    int cnt = 0;
    int maxCnt = 0;
    while (EOF != scanf("%s", string))
    {
        idx = 0;
        maxCnt = 0;
        cnt = 0;
        
        while (string[idx++] != '\0')
        {
            if (idx > 0 && string[idx] == string[idx - 1])
            {
                cnt = 2;
                left = idx - 1;
                right = idx;
            }
            else if (idx > 1 && string[idx] == string[idx - 2])
            {
                cnt = 3;
                left = idx - 2;
                right = idx;
            }
        
            while (left > 0 && 
                   string[right + 1] != '\0' &&
                   string[++right] == string[--left])
            {
                cnt += 2;
            }
        
            if (cnt > maxCnt) maxCnt = cnt;
            cnt = 0;
        }
        
        printf("%d\n", maxCnt);
    }
    
}

• just do it!~

#include <bits/stdc++.h>

using namespace std;

int checkSubstrValid(const string &input, int len, int left, int right) {
    bool isOdd = (left == right);
    int res;
    if (isOdd) {
        res = 1;
        --left;
        ++right;
    } else {
        res = 0;
    }
    for (; left >= 0 && right < len; --left, ++right) {
        if (input[left] == input[right]) {
            res += 2;
        } else {
            break;
        }
    }
    //cout << res << endl;
    return res;
}

int getMaxHuiwen(const string &input) {
    uint32_t n = input.length();
    if (n == 0 || n == 1) { return n; }
    int maxLen = 0;
    for (uint32_t i = 0; i < n-1; ++i) {
        maxLen = max(maxLen, checkSubstrValid(input, n, i, i));
        maxLen = max(maxLen, checkSubstrValid(input, n, i, i+1));
    }
    return maxLen;
}

int main () {
    string input;
    while (getline(cin, input)) {
        int res = getMaxHuiwen(input);
        if (res) { 
            cout << getMaxHuiwen(input) << endl;
        }
    }
    return 0;
}

package huaweitest;

import java.util.Scanner;

public class Main18 {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext()) {
            String s = cin.nextLine();
            int flag = 0, max = 0;
            //长度从最长开始
            for (int k = s.length(); k >= 1; k--) {
                int i = 0;
                //注意判断条件
                while (i + k <= s.length()) {
                    if (check(s.substring(i, i + k))) {
                        flag = 1;
                        max = k;
                        break;
                    }
                    i++;
                }
                if (flag == 1) {
                    break;
                }
            }
            System.out.println(max);
        }
    }

    public static boolean check(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}

while True:
    try:
        a = raw_input()
        m = len(a)
        dp = [[0]*m for _ in range(m)]
        ans = []
        for x in range(m):
            for y in range(m-x):
                i = y
                j = x + y
                if a[i] != a[j]:
                    dp[i][j] = 0
                else:
                    if j-i == 0:
                        dp[i][j] = 1
                    elif j-i == 1:
                        dp[i][j] = 2
                    else:
                        if dp[i+1][j-1] == 0:
                            dp[i][j] = 0
                        else:
                            dp[i][j] = dp[i+1][j-1] + 2
        for i in dp:
            ans.append(max(i))
        print max(ans)
    except:
        break