数据结构中子串该怎么计算

今天就跟大家聊聊有关数据结构中子串该怎么计算，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

一、说明

"回文串"是一个正读和反读都一样的字符串。
给定一个字符串 s ，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"

二、解决方案参考

1. Swift 语言

class LongestPalindromicSubstring {    func longestPalindrome(_ s: String) -> String {        guard s.characters.count > 1 else {            return s        }                var sChars = [Character](s.characters)        let len = sChars.count        var maxLen = 1        var maxStart = 0        var isPalin = Array(repeating: Array(repeating: false, count : len), count : len)                // set palindrome whose len is 1        for i in 0...len - 1 {            isPalin[i][i] = true        }                // set palindrome whose len is 2        for i in 0...len - 2 {            if sChars[i] == sChars[i + 1] {                isPalin[i][i + 1] = true                maxLen = 2                maxStart = i            }        }                if len >= 3 {            for length in 3...len {                for i in 0...len - length {                    if sChars[i] == sChars[i + length - 1] && isPalin[i + 1][i + length - 2] {                        isPalin[i][i + length - 1] = true                        maxLen = length                        maxStart = i                    }                }            }        }                return String(sChars[maxStart...maxStart + maxLen - 1])    }}

2. JavaScript 语言

/** * @param {string} s * @return {string} */// return the Longest Palindromic Substring of sfunction Manacher(s) {  var str = '*#'    , dp = []    , maxn = 0    , idx = 0;  for (var i = 0, len = s.length; i < len; i++)    str += s[i] + '#';  for (var i = 1, len = str.length; i < len; i++) {    if (maxn > i) dp[i] = Math.min(dp[2 * idx - i], maxn - i);    else dp[i] = 1;    while (str[i - dp[i]] === str[i + dp[i]]) dp[i]++;    if (dp[i] + i > maxn)      maxn = dp[i] + i, idx = i;  }  var ans = 0    , pos;  for (var i = 1; i < len; i++) {    if (dp[i] > ans)      ans = dp[i], pos = i;  }  var f = str[pos] === '#'    , tmp = f ? '' : str[pos]    , startPos = f ? pos + 1 : pos + 2    , endPos = f ? dp[pos] - 3 + startPos : dp[pos] - 4 + startPos;  for (var i = startPos; i <= endPos; i += 2)     tmp = str[i] + tmp + str[i];  return tmp;}var longestPalindrome = function(s) {  var str = Manacher(s);  return str;};

3. Python 语言

class Solution(object):    def longestPalindrome(self, s):        """        :type s: str        :rtype: str        """        left = right = 0        n = len(s)        for i in range(n - 1):            if 2 * (n - i) + 1 < right - left + 1:                break            l = r = i            while l >= 0 and r < n and s[l] == s[r]:                l -= 1                r += 1            if r - l - 2 > right - left:                left = l + 1                right = r - 1            l = i            r = i + 1            while l >= 0 and r < n and s[l] == s[r]:                l -= 1                r += 1            if r - l - 2 > right - left:                left = l + 1                right = r - 1        return s[left:right + 1]

4. Java 语言

public String longestPalindrome(String s) {    if (s == null || s.length() < 1) return "";    int start = 0, end = 0;    for (int i = 0; i < s.length(); i++) {        int len1 = expandAroundCenter(s, i, i);        int len2 = expandAroundCenter(s, i, i + 1);        int len = Math.max(len1, len2);        if (len > end - start) {            start = i - (len - 1) / 2;            end = i + len / 2;        }    }    return s.substring(start, end + 1);}private int expandAroundCenter(String s, int left, int right) {    int L = left, R = right;    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {        L--;        R++;    }    return R - L - 1;}

5. C++ 语言

#include #include #include #include using namespace std;string findPalindrome(string s, int left, int right){    int n = s.size();    int l = left;    int r = right;    while (left>=0 && right<=n-1 && s[left] == s[right]) {        left--;        right++;    }    return s.substr(left+1, right-left-1);}// This is the common solution.// Actuatlly it's faster than DP solution under Leetcode's test// the below optimized DP solution need 700ms+, this needs around 250ms.string longestPalindrome_recursive_way(string s) {    int n = s.size();    if (n<=1) return s;    string longest;        string str;    for (int i=0; i longest.size()){            longest = str;        }         str = findPalindrome(s, i, i+1);        if (str.size() > longest.size()){            longest = str;        }     }    return longest; }//================================================================================void findPalindrome(string s, int left, int right, int& start, int& len){    int n = s.size();    int l = left;    int r = right;    while (left>=0 && right<=n-1 && s[left] == s[right]) {        left--;        right++;    }    if (right-left-1 > len){        len = right-left-1;        start = left+1;    }}//The following solution is better than previous solution.//Because it remove the sub-string return in findPalindrome().string longestPalindrome_recursive_way2(string s) {    int n = s.size();    if (n<=1) return s;    int start=0, len=0;     string longest;    string str;    for (int i=0; i s[j] is Palindrome or not.    //using char or int could cause the `Memory Limit Error`    //vector< vector > matrix (n, vector(n));    //using bool type could cause the `Time Limit Error`    vector< vector > matrix (n, vector(n));    // Dynamic Programming     //   1) if i == j, then matrix[i][j] = true;    //   2) if i != j, then matrix[i][j] = (s[i]==s[j] && matrix[i+1][j-1])    for (int i=n-1; i>=0; i--){        for (int j=i; j 3, then, check s[i]==s[j] && matrix[i+1][j-1]            if ( i==j || (s[i]==s[j] && (j-i<2 || matrix[i+1][j-1]) ) )  {                matrix[i][j] = true;                if (longest.size() < j-i+1){                    longest = s.substr(i, j-i+1);                }            }        }    }    return longest;}// Optimized DP soltuion can be accepted by LeetCode.string longestPalindrome_dp_opt_way(string s) {    int n = s.size();    if (n<=1) return s;    //Construct a matrix, and consdier matrix[j][i] as s[i] -> s[j] is Palindrome or not.    //                                 ------^^^^^^    //                                 NOTE: it's [j][i] not [i][j]    //Using vector  could cause the `Time Limit Error`    //So, use the native array    bool **matrix  = (bool**)malloc(n*sizeof(bool*));    int start=0, len=0;    // Dynamic Programming    //   1) if i == j, then matrix[i][j] = true;    //   2) if i != j, then matrix[i][j] = (s[i]==s[j] && matrix[i-1][j+1])    for (int i=0; i 3, then, check s[i]==s[j] && matrix[i-1][j+1]            if ( i==j || (s[j]==s[i] && (i-j<2 || matrix[i-1][j+1]) ) )  {                matrix[i][j] = true;                if (len < i-j+1){                    start = j;                    len = i-j+1;                }            }        }    }    for (int i=0; i 1){        s = argv[1];    }    cout <<  s << " : " << longestPalindrome(s) << endl;    s = "321012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210123210012321001232100123210123";    cout <<  s << " : " << longestPalindrome(s) << endl;     //"illi"    s = "iptmykvjanwiihepqhzupneckpzomgvzmyoybzfynybpfybngttozprjbupciuinpzryritfmyxyppxigitnemanreexcpwscvcwddnfjswgprabdggbgcillisyoskdodzlpbltefiz";    cout <<  s << " : " << longestPalindrome(s) << endl;    return 0;}

6. C 语言

#include #include #include static inline int min(int a, int b){    return a < b ? a : b;}static int manacher(char *s, char output[]){    int i, j;    char s2[3000] = { '\0' };    s2[0] = '$';    for (i = 0; s[i] != '\0'; i++) {        s2[(i<<1)+1] = '#';        s2[(i<<1)+2] = s[i];    }    s2[(i<<1)+1] = '#';    int len = (i<<1)+2;    s2[len] = '\0';        int p[3000] = { 0 }; // 以s2中某一点为中心的回文半径    int id = 0; // 回文的中心点    int limit = 0; // 最长回文的右边界点    int maxLen = 0; // 最大回文长度    int maxId = 0; // 最长回文的中心点    for (i = 1; i < len; i++) {        if (i < limit) {            p[i] = min(p[2*id-i], limit-i);        } else {            p[i] = 1;        }                while (s2[i+p[i]] == s2[i-p[i]]) {            p[i]++;        }                if (i+p[i] > limit) {            limit = i+p[i];            id = i;        }        if (maxLen < p[i]-1) {            maxLen = p[i]-1;            maxId = i;        }    }        for (j = 0, i = maxId - maxLen; i <= maxId+maxLen; i++) {        if (s2[i] != '#') {            output[j++] = s2[i];        }    }    return maxLen;}static char *longestPalindrom(char *s){    int i;    if (s == NULL) {        return NULL;    }    int len = strlen(s);    if (len <= 1) {        return s;    }    char *palindrome = malloc(2000);    memset(palindrome, 0, sizeof(palindrome));    int size = manacher(s, palindrome);    palindrome[size] = '\0';    return palindrome;}int main(int argc, char **argv){    if (argc != 2) {        fprintf(stderr, "Usage: ./test string");        exit(-1);    }    printf("%s", longestPalindrom(argv[1]));    return 0;}

看完上述内容，你们对数据结构中子串该怎么计算有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注行业资讯频道，感谢大家的支持。