回文子串

字符串的回文串总结

一看到回文字符串，脑海里立马要想到前面两个最常用的结题思路:

• 1.动态规划
• 2.中心扩散法
• 3.还有著名的马拉车算法

leetcode出现的回文字符串的三个题：

• 1.回文子串的个数
• 2.最长回文子串
• 3.最长不连续的回文子串

1.回文子串的个数——本题

public class Solution14_回文子串 {
    /**
     * 方法一：中心扩散法
     */
    static int ans = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        for (int i = 0; i < s.length(); i++) {
            //考虑两种情况：aba 和 abba
            centerSpread(s, i, i);
            centerSpread(s, i, i + 1);
        }
        System.out.println(ans);
    }

    //判断回文串的中心扩散法
    private static void centerSpread(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
            ans++;
        }
    }

    //方法二：动态规划
    private static int dp(String s) {
        int n = s.length(), ans = 0;
        boolean[][] dp = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i <= 2 || dp[i + 1][j - 1]);
                if (dp[i][j]) ans++;
            }
        }
        return ans;
    }
}

2.最长回文子串

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
Input: "cbbd"
Output: "bb"

class Qusetion2 {

    //1.动态规划
    public static String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;
        int maxLen = 1;
        String res = s.substring(0, 1);
        boolean[][] dp = new boolean[n][n];
        //左边界一定小于右边界，因此从右边界开始
        for (int r = 1; r < n; r++) { //表示右边界
            for (int l = 0; l < r; l++) { //表示左边界
                // 区间应该慢慢放大
                // 状态转移方程：如果头尾字符相等并且中间也是回文
                // 在头尾字符相等的前提下，如果收缩以后不构成区间（最多只有 1 个元素），直接返回 True 即可
                // 否则要继续看收缩以后的区间的回文性
                if (s.charAt(l) == s.charAt(r) && ((r - l) <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        res = s.substring(l, r + 1);
                    }
                }
            }
        }
        return res;
    }

    //2.中心扩展法
    private int start, maxLen;

    public String longestPalindrome1(String s) {
        if (s == null || s.length() < 2) return s;
        for (int i = 0; i < s.length(); i++) {
            //考虑中心扩散的两种情况1:aba  和 2: bb
            findMaxPalindrome(s, i, i);
            findMaxPalindrome(s, i, i + 1);
        }
        return s.substring(start, start + maxLen);
    }

    private void findMaxPalindrome(String s, int i, int j) {
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;//向左延伸
            j++;//向右延伸
        }
        //记录每个起始点扩展的回文串的最大长度
        if (maxLen < j - i - 1) {
            start = i + 1;
            maxLen = j - i - 1;
        }
    }
}

3.最长不连续回文子串

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:
"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".

    public int longestPalindrome(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];//dp[l][r]表示l-r中的最长回文串
        for (int r = 0; r < n; r++) {
            dp[r][r] = 1;
            for (int l = r - 1; l >= 0; l--) {
                if (s.charAt(l) == s.charAt(r)) {
                    dp[l][r] = dp[l + 1][r - 1] + 2;
                } else {
                    dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }

//不喜欢dp的看这里
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string str;
    while (cin >> str)
    {
        int len = str.size();
        int count = 0;
        for (int i = 1; i<len; i++)
        {
            if (str[i - 1] == str[i + 1])
            {
                count++;
                for (int j = 1; j <= (len - i) && j<i; j++)
                {
                    if (str[i +1+ j] == str[i - 1 - j])
                    {
                        count++;
                    }
                    else
                    {
                        break;
                    }
                }
            }
            if (str[i] == str[i - 1])
            {
                count++;
                for (int j = 1; j <= (len - i) && j<i; j++)
                {
                    if (str[i + j] == str[i - 1 - j])
                    {
                        count++;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
        cout << count + len << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.next();
        // 从中心向两边扩散
        int result = 0;
        int i = 0;
        while (i < input.length()) {
            // 以i位置的字符为中心
            // 首先i位置字符本身肯定是一个回文串
            result++;
            for (int j = 1; i - j >= 0 && i + j < input.length(); ++j) {
                if (input.charAt(i - j) == input.charAt(i + j)) {
                    ++result;
                } else {
                    break;
                }
            }

            // 以i右边的间隔为中心
            // 若i是最后一个字符就无需进行这一步了
            if (i == input.length() - 1) {
                break;
            }
            for (int j = 0 ; i - j >= 0 && i + j + 1 < input.length(); ++j) {
                if (input.charAt(i - j) == input.charAt(i + j + 1)) {
                    ++result;
                } else {
                    break;
                }
            }
            ++i;
        }
        System.out.println(result);
    }
}

/*
数据小，暴力判断应该也可以过。
动态规划。
dp[i]表示前i个字符中包含的回文子串。
dp[i] = dp[i-1] + 新增。
突然想到：这样写和暴力完全没区别。
*/
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        int len = s.length();
        int[] dp = new int[len + 1];   //表示前i个字符中有多少个回文子串。
        dp[0] = 0;
        dp[1] = 1;
        int cnt = 0;   //记新加一个字符增加的回文子串数量。
        for (int i = 2; i <= len; i++) {
            cnt = 0;
            for (int loc = 0; loc < i - 1; loc++) {
                if (s.charAt(loc) == s.charAt(i - 1)) {
                    if (isBackString(s.substring(loc, i)))
                        cnt++;
                }
            }
            dp[i] = dp[i - 1] + cnt + 1;
        }
        System.out.println(dp[len]);
    }

    static boolean isBackString(String s) {
        int len = s.length();
        int head = 0;
        int end = len - 1;
        while (head < end) {
            if (s.charAt(head) != s.charAt(end))
                return false;
            head++;
            end--;
        }
        return true;
    }
}

import java.util.*;
/*
利用indexof和substring方法来进行操作
依次把首尾相同的字符串进行回文数判断
*/
public class Main{
    public static boolean isHui(String str){
        if(str.length()<=1)return true;
        int left = 0,right = str.length()-1;
        while(left<right){
            if(str.charAt(left)==str.charAt(right)){
                left++;
                right--;
            }else
                return false;
        }
        return true;
    }
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String str = input.next();
        int count = str.length();
        for(int i = 0;i<str.length()-1;i++){
            String substr = str.substring(i+1);
            while(substr.contains(Character.toString(str.charAt(i)))){
                String subsubstr = substr.substring(i,substr.indexOf(str.charAt(i))+1);
                if(isHui(subsubstr))
                    count++;
                substr = substr.substring(substr.indexOf(str.charAt(i))+1);
            }
        }
        System.out.println(count);
    }
    
}

//就硬解
#include <stdio.h>
#include <string.h>
int main(){
    char s[50],len;
    scanf("%s", &s);
    len = strlen(s);
    int count1 = 0;
    /*
    采用遍历的方式，以当前位置为起点不断增加字符串的长度
    对这一段字符串进行是否为回文的判断（首位与末尾，首位不断推后，末尾不断推前）
    中间如若有一对字符对不上则这一段判断结束
    只有当这部分字符串全部都被判断后，才能认为此段为回文，计数+1
    */
    for(int i = 0; i < len;i++){
        for(int j = 1;j+i < len;j++){
            for(int k = 0;i+k<=i+j-k+1;k++){
                if(s[i+k] != s[i+j-k])
                    break;
                if(2*k >= j)
                    count1++;
            }
        }
    }
    printf("%d",count1+len);  //回文数加上字符串长度
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int F(string s){
    int l = s.length();
    int i=0,j=l-1;
    while(i<l)
        if(s[i++]!=s[j--])
            return 0;
    return 1;
}

int main(){
    string s;
    cin>>s;
    int n = s.length(), r=n;
    for(int i=0;i<n;i++){
        for(int l=2;i+l<=n;l++){
            string t = s.substr(i, l);
            r += F(t);
        }
    }
    cout<<r<<endl;
    return 0;
}

// 数据量为 50， 因此可用 O(N^3)

#include<bits/stdc++.h>
using namespace std;
string str;
bool f(int l, int r) {
	while (l < r) {
		if (str[l++] != str[r--]) {
			return false;
		}
	}
	return true;
}
int main() {
	cin >> str;
	auto lens = str.length();
	int ans = lens;
	for (auto len = 2; len<=lens; ++len) {
		for (int i=0; i+len-1<lens; ++i) {
			if (f(i, i+len-1)) {
				++ans;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

public class Main {
    //蛮力法
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int n = str.length();
        int count = n;
        for (int i=0;i<n;i++){
            for (int j=i+1;j<n;j++){
                if (judge(str,i,j))
                    count++;
            }
        }
        System.out.println(count);
    }
    private static boolean judge(String str,int i,int j){
        while (i < j){
            if (str.charAt(i) != str.charAt(j))
                return false;
            i++;j--;
        }
        return true;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int n = str.length();
        int count = n;
        int[][] dp = new int[n][n];
        dp[0][0] = 1;
        for (int j=1;j<n;j++){
            dp[j][j] = 1;
            for (int i=j-1;i>=0;i--){
                if (str.charAt(i) == str.charAt(j) && (i+1 > j-1 || dp[i+1][j-1] == 1)){
                    dp[i][j] = 1;
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

/*
暴力枚举 
*/
#include<bits/stdc++.h>
using namespace std;
#define N 1000

int main()
{
//    freopen("input.txt", "r", stdin);
    int n, i, j, k, ans = 0;
    char s[N];
    cin >> s;
    n = strlen(s);
    for(k = 0; k < 2 * n - 1; k++) {
        i = int(k / 2);
        j = k - i;
        while(i >= 0 && j < n && s[i] == s[j]) {
            ans++;
            i--;
            j++;
        }
    }
    cout << ans << endl;
    return 0;
}

str = input()

#  判断是否是回文
def is_palindrome(str):
    is_palindrome_flag = True
    for i in range(len(str) // 2):
        if str[i] is not str[-i - 1]:
            is_palindrome_flag = False
    return is_palindrome_flag

res = 0
# 将str变成二维，找到str[x：y+1]的切片
for x in range(0, len(str)):
    for y in range(x, len(str)):
        if is_palindrome(str[x:y + 1]):
            res += 1

print(res)

import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc= new Scanner(System.in);
String str = sc.next();
int sum=0;
for (int i = 0; i < str.length(); i++)
for (int j = i+1; j <=str.length(); j++)
{
String str1=str.substring(i, j);
if(str1.equals( new StringBuffer(str1).reverse().toString()))
sum++;
}
System.out.println(sum);
}
}
算是暴力枚举了，中间感觉还可以优化一些，就是借助java的函数，截取字符，然后翻转对比！

其实还有一种开枝散叶的算法，就是每次以一个字符为中心，先往右看，找相同的，如果有，就每找到一个就总数加1，直到找不到了，然后再看左边有没有使得左右相等的。这个代码也不复杂！我就不写了，有想法的可以实现下！

比如给的例子：aabcb

先加赋值sum等于字符串的长度，先把每个单独字符成的回文算下，这时候sum=5：

先从第一个a看，右边有一个跟它一样的，所以sum++，sum这时为6.

再往后看，一个b，不符合。

然后往左边看，左边没有了。好，看第二个字符。

第二个字符是a，同样，右看，没有！

左看，a和右边的b不相等！

看下一个，也就是b

右看，b不等于c，没有！

左看，a和c不相等，没有！

然后看c，右看，没有！

左看！b等于b！好sum++，这时sum=7；

继续左看，右边跑数组外面去了，不符合！

再看最后那个b，右边跑数组外面去了，不符合！

看左边，右边跑出去了，不符合！

这样就完了吧！

呵呵，还没完，中间有个坑，要填一下，如aaa，第一个里a往右看有个aaa，第二个a往左看，左右有个aaa，这不是就重复计算了么？

所以往左看的时候，要仔细判断！

这个自己解决下吧！

import sys
def isHuiwen(string):
    if len(string)==1:
        return True
    i,j = 0,len(string)-1
    while i<j:
        if string[i] != string[j]:
            return False
        i+=1
        j-=1
    return True
def countNum(string):
    res = 0
    for i in range(len(string)-1,-1,-1):
        if isHuiwen(string[i:len(string)]):
            res+=1
    return res
while True:
    #动态规划问题：
    #dp[i]表示在第i个位置时字符串有多少个回文子串
    #状态转移方程：
    #dp[i+1] = dp[i] + countNum(str[:i])
    string = input().strip()
    dp=[0 for _ in range(len(string))]
    dp[0]=1
    for i in range(1,len(string)):
        dp[i] = dp[i-1]+countNum(string[:i+1])
    print(dp[-1])

def num_substr(s):
    res = 0
    if len(s)<=1:
        print(len(s))
        return len(s)
    for length in range(len(s),0,-1):
        for i in range(len(s)-length+1):
            now_s = s[i:i+length]
            if now_s == now_s[::-1]:
                res+=1
    print(res)
    return res

if __name__ == '__main__':
    import sys
    s = sys.stdin.readline().strip()
    num_substr(s)

最长回文串的变型

#include <iostream>
(720)#include <vector>
#include <string>
using namespace std;

int main(){

    string s;
    cin >> s;
    int len = s.size();
    int ans = 0;
    vector<vector<int>> dp(len,vector<int>(len,0));
    for(int i = 0;i < len;i++){
        dp[i][i] = 1;
        ans++;
    }
    for(int i = len-2;i >= 0;i--){
        for(int j = i+1;j <= len-1;j++){
            if(s[i] == s[j]){
                dp[i][j] = dp[i+1][j-1] + 2;
            }else{
                dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
            }
            if((j-i+1) == dp[i][j]){
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}