數(shù)據(jù)結(jié)構(gòu)中子串該怎么計算-四川平武建站

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

數(shù)據(jù)結(jié)構(gòu)中子串該怎么計算

今天就跟大家聊聊有關(guān)數(shù)據(jù)結(jié)構(gòu)中子串該怎么計算，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

在瓊山等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站設(shè)計、做網(wǎng)站、成都外貿(mào)網(wǎng)站建設(shè)公司網(wǎng)站設(shè)計制作定制開發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站設(shè)計,網(wǎng)絡(luò)營銷推廣,外貿(mào)營銷網(wǎng)站建設(shè),瓊山網(wǎng)站建設(shè)費用合理。

一、說明

“回文串”是一個正讀和反讀都一樣的字符串。
給定一個字符串 s ，找到 s 中最長的回文子串。你可以假設(shè) 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 s
function 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;
}

看完上述內(nèi)容，你們對數(shù)據(jù)結(jié)構(gòu)中子串該怎么計算有進一步的了解嗎？如果還想了解更多知識或者相關(guān)內(nèi)容，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝大家的支持。

分享文章：數(shù)據(jù)結(jié)構(gòu)中子串該怎么計算
文章源于：http://www.ef60e0e.cn/article/gddics.html

99热在线精品一区二区三区_国产伦精品一区二区三区女破破_亚洲一区二区三区无码_精品国产欧美日韩另类一区

新聞中心

一、說明

二、解決方案參考

其他資訊