马拉车算法寻找字符串最大回文串

本文主要是介绍马拉车算法寻找字符串最大回文串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    int getLongestPalindrome(string A, int n) {
        // write code here
        char* s2 = (char*)malloc(2 * n + 1);
        int* tempLen = (int*)malloc((2 * n + 1) * 4);
        //int tempLen[219*2+1] = { 0 };
        for (int i = 0; i < (2 * n + 1); i++) {
            if (i % 2) {
                s2[i] = A[i / 2];
            }
            else {
                s2[i] = '#';
            }
            tempLen[i] = 0;
        }

        int curMaxRightIndex = 0; //现有字符回文能到达的最右边索引
        int centerIndexOfCurMaxRightIndex = 0; //到达最右边索引的中心索引值
        int maxLen = 0;  //最大回文半径，非原始字符串
        for (int i = 0; i < (2 * n + 1); i++) {
            if (i < curMaxRightIndex ) {
                tempLen[i] = min(tempLen[2 * centerIndexOfCurMaxRightIndex - i], curMaxRightIndex - i);
            }
            else {
                tempLen[i] = 1;
            }
            for (; (i - tempLen[i] >= 0) && (i + tempLen[i] < 2 * n + 1) && (s2[i - tempLen[i]] == s2[i + tempLen[i]]); tempLen[i]++);

            if (i + tempLen[i] > curMaxRightIndex) {
                curMaxRightIndex = i + tempLen[i];
                centerIndexOfCurMaxRightIndex = i;
            }
            if (maxLen <= tempLen[i]) {
                maxLen = tempLen[i];
            }
        }

        return maxLen - 1;
    }
};

int main() {

    string s("dbadddadbbaabbcbcddbabacbdccdcbaddccdaacdccbcdaadadccbdbabddaaddbddbdaddbaadbabcaabccbacaacdaddbaadbadbbccababaaccbbbcccbbdbbdacbcaacaddccbbdbbbdacdbbdccaaddcdbadabdcbabcabbccdbdabbbaabacabababcbbcdcdcbbdcdcadbcaadaddcb");
    cout << sizeof(int) << endl;
    Solution so;
    int len = 0;
    len = so.getLongestPalindrome(s, 219);
    cout << len << endl;

    return 0;
}

这篇关于马拉车算法寻找字符串最大回文串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！