HDU - 3068 最长回文【马拉车】题解

冷不防 2021-07-24 23:06 347阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.代码

### 1.题目 ###

给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.  
回文就是正反读都是一样的字符串,如aba, abba等  
Input  
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c…y,z组成的字符串S  
两组case之间由空行隔开(该空行不用处理)  
字符串长度len <= 110000  
Output  
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.  
Sample Input

aaaa
    abab

Sample Output

4
    3

### 2.代码 ###

///马拉车算法]
    #define _CRT_SECURE_NO_WARNINGS 
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int  maxn = 1e7 + 10;
    char str[maxn];  ///原字符串
    char tmp[maxn];  ///转换后的字符串
    int len[maxn];  ///辅助数组
    int INIT(char *st)//转换字符串
    { 
    	int i, len = strlen(st);
    	tmp[0] = '@';  ///开头特殊字符，防止越界
    	for (i = 1; i <= 2 * len; i += 2)
    	{ 
    		tmp[i] = '#';
    		tmp[i + 1] = st[i / 2];
    	}
    	tmp[2 * len + 1] = '#';
    	tmp[2 * len + 2] = '$';  //结尾特殊字符,防止越界
    	tmp[2 * len + 3] = 0;
    	return 2 * len + 1;
    }
    ///马拉车算法
    int  MANACHER(char *st, int Len)
    { 
    	int mx = 0, ans = 0, po = 0;///mx即为当前计算回文串最右边字符的最大追
    	for (int i = 1; i<= Len; i++)
    	{ 
    		if (mx > i)
    			len[i] = min(mx - i, len[2 * po - i]);///在len[j]和mx-i中取最小
    		else
    			len[i] = 1; i>.=mx,要从头开始匹配
    		while (st[i - len[i] ]== st[i + len[i]])
    			len[i]++;
    		if (len[i] + i > mx)//新计算的回文串右端点位置大于mx，更新po和mx
    		{ 
    			mx = len[i] + i;
    			po = i;
    		}
    		ans = max(ans, len[i]);
    	}
    	return ans - 1; ///len[i]最大值-1即为原回文串的最大长度
    }
    int  main()
    { 
    	while (scanf("%s", str) != EOF)
    	{ 
    		int len=INIT(str);
    		printf("%d\n",MANACHER(tmp, len));
    	}
    	return 0;
    }