void connect(TreeLinkNode *root) {
    if (root == NULL) return;
    TreeLinkNode *pre = root;
    TreeLinkNode *cur = NULL;
    while(pre->left) {
        cur = pre;
        while(cur) {
            cur->left->next = cur->right;
            if(cur->next) cur->right->next = cur->next->left;
            cur = cur->next;
        }
        pre = pre->left;
    }
}

void connect(TreeLinkNode *root) {
    TreeLinkNode *now, *tail, *head;

    now = root;
    head = tail = NULL;
    while(now)
    {
        if (now->left)
            if (tail) tail = tail->next =now->left;
            else head = tail = now->left;
        if (now->right)
            if (tail) tail = tail->next =now->right;
            else head = tail = now->right;
        if(!(now = now->next)) // now没有后继，跳到下一行最左边的节点
        {
            now = head;
            head = tail=NULL;  // head和tail设置为null
        }
    }
}

public class Solution {
    public List<List<Integer>> permute(int[] num) {
         List<List<Integer>> result = new ArrayList<List<Integer>>(); 
         permute(num,0,result);
         return result;
    }

    public void permute(int[] num, int begin, List<List<Integer>> result){
        if(begin>=num.length){
            List<Integer> list = new ArrayList<Integer>();
            for(int i=0;i<num.length;i++){
                list.add(num[i]);
            }
            result.add(list);
            return;
        }
        for(int i=begin;i<num.length;i++){
            swap(begin,i,num);
            permute(num,begin+1,result);
            swap(begin,i,num);
        }
    }

    public void swap (int x, int y,int[] num){
        int temp = num[x];
        num[x]=num[y];
        num[y]=temp;
    }
}

public class Solution {
    public String getPermutation(int n, int k) {
        int pos = 0;
        List<Integer> numbers = new ArrayList<>();
        int[] factorial = new int[n+1];
        StringBuilder sb = new StringBuilder();

        // create an array of factorial lookup
        int sum = 1;
        factorial[0] = 1;
        for(int i=1; i<=n; i++){
            sum *= i;
            factorial[i] = sum;
        }
        // factorial[] = {1, 1, 2, 6, 24, ... n!}
        // create a list of numbers to get indices
        for(int i=1; i<=n; i++){
            numbers.add(i);
        }
        // numbers = {1, 2, 3, 4}

        k--;
        for(int i = 1; i <= n; i++){
            int index = k/factorial[n-i];
            sb.append(String.valueOf(numbers.get(index)));
            numbers.remove(index);
            k-=index*factorial[n-i];
        }
        return String.valueOf(sb);
    }
}

public class Solution {
    public int maximumGap(int[] num) {
        if (num.length < 2) return 0;
        int N=num.length,bucketSize=0,bucketNum=0,minElement=Integer.MAX_VALUE,maxElement=0;
        // 确定最值
        for (int i=0; i<N; i++) {
            minElement = Math.min(minElement, num[i]);
            maxElement = Math.max(maxElement, num[i]);
        }
        bucketSize = (int)Math.ceil(((double)(maxElement-minElement))/(N-1)); // bucket的大小
        bucketNum  = (int)Math.ceil(((double)(maxElement-minElement))/bucketSize); // bucket数量
        int[] bucketMax = new int[bucketNum+1],bucketMin = new int[bucketNum+1];
        for (int i=0; i<=bucketNum; i++) {
            bucketMax[i]=Integer.MIN_VALUE;
            bucketMin[i]=Integer.MAX_VALUE;
        }
        for (int i=0; i<N; i++) {  //put elements in buckets
            if (num[i]==minElement || num[i]==maxElement) // 不加入最值
                continue;
            int bucketId = (int) Math.ceil(((double)(num[i]-minElement))/bucketSize); // 计算bucket编号
            bucketMax[bucketId] = Math.max(num[i], bucketMax[bucketId]);
            bucketMin[bucketId] = Math.min(num[i], bucketMin[bucketId]);
        }
        int maxGap=0, temp=minElement; // temp设置为最小值，可以捕捉最小值和第二小值之间的gap
        // 在bucket之间寻找最大gap
        for (int i=1; i<=bucketNum; i++) {
            if (bucketMin[i]==Integer.MAX_VALUE)
                continue;
            if (maxGap < bucketMin[i]-temp) {
                maxGap = bucketMin[i]-temp;
            }
            temp = bucketMax[i];
        }
        maxGap = Math.max(maxGap, maxElement-temp); 捕捉最大和第二大值之间的gap
        return maxGap;
    }
}

public class Solution {
private int lo, maxLen;

public String longestPalindrome(String s) {
    int len = s.length();
    if (len < 2)
        return s;
    for (int i = 0; i < len-1; i++) {
         extendPalindrome(s, i, i);  //assume odd length
         extendPalindrome(s, i, i+1); //assume even length
    }
    return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
    while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
        j--;
        k++;
    }
    if (maxLen < k - j - 1) {
        lo = j + 1;
        maxLen = k - j - 1;
    }
}}

S     #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #
P     1   2  1  2  5   2  1  4   1  2  1  6   1  2   1  2  1
P[i]-1正好是原字符串中回文串的总长度

#include <iostream>
#include <string>
#include<algorithm>
using namespace std;
// 将字符串处理，比如abcd变成：$#a#b#c#d#.
// 这样可以将奇数长度的回文和偶数长度回文一起处理。
string preProcess(string & str) {
    string ret="$#";
    for (int i=0; i<str.length(); i++) {
        ret += str[i];
        ret += "#";
    }
    return ret;
}
int p[2000009]={0};
void getMaxLength(string str) {
    // mostFar记录了i之前回文到达的最右坐标
    // id是与之对应的中心坐标。 p记录的是以i为中心的回文半价，单个字母为1. 
    int id=0, mostFar=0, maxL=0;
    p[0] = 0;
    for (int i=1; i<str.length(); i++) {
        if (mostFar > i) {
            int j=2*id-i; // j and i are symmetric by id.
            if (p[j] < mostFar-i) // extension needed
                p[i] = p[j];
            else
                p[i] = mostFar-i; // extension needed
        } else
            p[i] = 1;
        // extension
        while ((i+p[i]<str.length()) && (i-p[i]>=0) && str.at(i+p[i]) == str.at(i-p[i]))
            ++p[i];
        if (p[i]+i > mostFar) { // update mostFar and id.
            mostFar = (p[i]+i);
            id = i;
        }
    }
    for (int i=0; i<str.length(); i++)
        maxL = max(maxL, p[i]);
    cout<<maxL-1<<endl;
}
int main() {
    int n=0;
    cin>>n;
    string str="";
    for (int i=0; i<n; i++) {
        cin>>str;
        if (str.length() < 2)
            cout<<str.length()<<endl;
        else {
            str = preProcess(str);
            getMaxLength(str);
        }
    }
    return 0;
}

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        vector<int> s;
        int ret = 0;
        height.push_back(0);
        for (int i=0; i<height.size(); i++) {
            while (s.size()>0 && height[s.back()]>=height[i]) {
                int h = height[s.back()], sid=0;
                s.pop_back();
                if (s.size() == 0)
                    sid = 0;
                else
                    sid = s.back()+1;
                if (ret < h*(i-sid))
                    ret = h*(i-sid);
            }
            s.push_back(i);
        }
        return ret;
    }
}

* J(y)：在状态y时的评价函数值
* Y(i)：表示当前状态
* Y(i+1)：表示新的状态
* r： 用于控制降温的快慢
* T： 系统的温度，系统初始应该要处于一个高温的状态
* T_min ：温度的下限，若温度T达到T_min，则停止搜索

while( T > T_min ) {
    dE = J( Y(i+1) ) - J( Y(i) ) ;
    if ( dE >=0 ) //表达移动后得到更优解，则总是接受移动
        Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
    else {
        // 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也
        if ( exp( dE/T ) > random( 0 , 1 ) )
            Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
    }
    T = r * T ; //降温退火 ，0 < r < 1 。r越大，降温越慢；r越小，降温越快
    /*
    * 若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值
    */
    i++ ;
}

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    int i=0;
    // 把能合并的区间之前的区间skip
    while (i<intervals.size() && intervals.get(i).end<newInterval.start) i++;
    // 把能合并的区间删除
    while (i<intervals.size() && intervals.get(i).start<=newInterval.end) {
        newInterval = new Interval(Math.min(intervals.get(i).start, newInterval.start), Math.max(intervals.get(i).end, newInterval.end));
        intervals.remove(i);
    }
    // 添加合并完的集合
    intervals.add(i,newInterval);
    return intervals;
}

class Solution {
public:
    int maxArea(vector<int> &height) {
        int i=0, j=height.size()-1, maxArea=0;
        while (i < j) {
            maxArea = max(maxArea, (j-i)*min(height[i],height[j]));
            if (height[i] <= height[j])
                ++i;
            else
                --j;
        }
        return maxArea;
    }
}

void preOrder(TreeNode *root) {    //非递归前序遍历
    stack<TreeNode*> s;
    TreeNode *p=root;
    while (p || !s.empty()) {
        if (p != NULL) { // 使劲向左
            visit(p);
            s.push(p);
            p = p->left;
        } else {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}

void inOrder(TreeNode *root) {  //非递归中序遍历
    stack<TreeNode*> s;
    TreeNode *p = root;
    while (p != NULL || !s.empty()) {
        if (p != NULL) { // 使劲向左
            s.push(p);
            p = p->left;
        } else {
            p = s.top();
            s.pop();
            visit(p);
            p = p->right;
        }
    }
}

void postOrder(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode *p = root;
    TreeNode *pre = NULL; // last visited
    while (p != NULL || !s.empty()) {
        if (p != NULL) { // 使劲向左
            s.push(p);
            p = p->left;
        } else {
            p = s.top();
            // 右孩子为空或者刚刚访问过了，可以访问当前节点了
            if (p->right == NULL || pre == p->right) {
                s.pop();
                visit(p);
                pre = p;
                p = NULL; // 不置空就重复访问了
            } else { // 否则访问右孩子
                p = p->right;
            }
        }
    }
}

void postOrder(TreeNode *root) {  //非递归后序遍历
    stack<TreeNode*> sTraverse, sVisit;
    sTraverse.push(root);
    while(!s.empty()) {
        TreeNode * p = sTraverse.top();
        sTraverse.pop();
        sVisit.push(p);
        if (p->left) sTraverse.push(p->left);
        if (p->right) sTraverse.push(p->right);
    }
    while (!sVisit.empty()) {
        visit(sVisit.top());
        sVisit.pop();
    }
}

num[i,j] = min(num[i,k]+num[k+1,j])

public class Solution {
    public int minCut(String s) {
        int[] num = new int[s.length()+1];
        for (int i = 0; i <= s.length(); i++) num[i] = i-1;
        for (int i = 0; i < s.length(); i++) {
            // 奇数回文子串
            for (int j=0; i-j>=0 && i+j<s.length() && s.charAt(i-j)==s.charAt(i+j); j++)
                num[i+j+1] = Math.min(num[i+j+1], num[i-j]+1);
            // 偶数回文子串
            for (int j=0; i-j>=0 && i+j+1<s.length() && s.charAt(i-j)==s.charAt(i+j+1); j++)
                num[i+j+2] = Math.min(num[i+j+2], num[i-j]+1);
        }
        return num[s.length()];
    }
}