A.ABB（Manacher）

本文主要是介绍A.ABB（Manacher），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接
https://ac.nowcoder.com/acm/problem/209398

题目描述
Fernando was hired by the University of Waterloo to finish a development project the university started some time ago. Outside the campus, the university wanted to build its representative bungalow street for important foreign visitors and collaborators.
Currently, the street is built only partially, it begins at the lake shore and continues into the forests, where it currently ends. Fernando’s task is to complete the street at its forest end by building more bungalows there. All existing bungalows stand on one side of the street and the new ones should be built on the same side. The bungalows are of various types and painted in various colors.
The whole disposition of the street looks a bit chaotic to Fernando. He is afraid that it will look even more chaotic when he adds new bungalows of his own design. To counterbalance the chaos of all bungalow shapes, he wants to add some order to the arrangement by choosing suitable colors for the new bungalows. When the project is finished, the whole sequence of bungalow colors will be symmetric, that is, the sequence of colors is the same when observed from either end of the street.
Among other questions, Fernando wonders what is the minimum number of new bungalows he needs to build and paint appropriately to complete the project while respecting his self-imposed bungalow color constraint.
输入描述:
The first line contains one integer N (1 ≤ N ≤ 4·105 ), the number of existing bungalows in the street. The next line describes the sequence of colors of the existing bungalows, from the beginning of the street at the lake. The line contains one string composed of N lowercase letters (“a” through “z”), where different letters represent different colors.
输出描述:
Output the minimum number of bungalows which must be added to the forest end of the street and painted appropriately to satisfy Fernando’s color symmetry demand.
示例1
输入
3
abb
输出
1
示例2
输入
12
recakjenecep
输出
11
示例3
输入
15
murderforajarof
输出
6

题意
给你一个字符串，问你末尾最少加几个字符能成为一个回文串？

思路
很容易想到判断子串能不能成为一个回文子串，不过这个子串得到末尾，很容易想到马拉车，那么就是在其模板上魔改就行了。
具体是我们用马拉车求出len数组，然后从头开始判断这个子串是不是回文且到末尾。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 5;
const ll mod = 1e9 + 7;int Case,n;char s[N * 2], str[N * 2];
int Len[N * 2];
void getstr() {//重定义字符串int k = 0;str[k++] = '@';//开头加个特殊字符防止越界for (int i = 0; i < n; i++) {str[k++] = '#';str[k++] = s[i];}str[k++] = '#';n = k;str[k] = 0;//字符串尾设置为0，防止越界
}
void manacher() {int mx = 0, id;//mx为最右边，id为中心点for (int i = 1; i < n; i++) {if (mx > i) Len[i] = min(mx - i, Len[2 * id - i]);//判断当前点超没超过mxelse Len[i] = 1;//超过了就让他等于1，之后再进行查找while (str[i + Len[i]] == str[i - Len[i]]) Len[i]++;//判断当前点是不是最长回文子串，不断的向右扩展if (Len[i] + i > mx) {//更新mxmx = Len[i] + i;id = i;//更新中间点}}
}void solve(){scanf("%d",&n);int t = n;scanf("%s",s);getstr();manacher();for(int i=1;i<n;i++){if(Len[i]+i==n){printf("%d",max(0,t-Len[i] + 1));return;}}
}int main(){Case = 1;//scanf("%d",&Case);while(Case--){solve();}
}

这篇关于A.ABB（Manacher）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---