题意:
求最长回文串 长度要大于等于 2 且输出起点和终点 输出回文串字符 这个字符还是要以给出的字符为起点 a 输出
解析:
分析一下 s_new 串就好了
- #include <iostream>
- #include <cstdio>
- #include <sstream>
- #include <cstring>
- #include <map>
- #include <set>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #define rap(i, a, n) for(int i=a; i<=n; i++)
- #define rep(i, a, n) for(int i=a; i<n; i++)
- #define lap(i, a, n) for(int i=n; i>=a; i--)
- #define lep(i, a, n) for(int i=n; i>a; i--)
- #define rd(a) scanf("%d", &a)
- #define rlld(a) scanf("%lld", &a)
- #define rc(a) scanf("%c", &a)
- #define rs(a) scanf("%s", a)
- #define MOD 2018
- #define LL long long
- #define ULL unsigned long long
- #define Pair pair<int, int>
- #define mem(a, b) memset(a, b, sizeof(a))
- #define _ ios_base::sync_with_stdio(0),cin.tie(0)
- //freopen("1.txt", "r", stdin);
- using namespace std;
- const int maxn = 200010, INF = 0x7fffffff;
- char s[maxn], s_new[maxn<<1];
- int p[maxn<<1];
- int tmp;
- int init()
- {
- int len = strlen(s);
- s_new[0] = '$';
- s_new[1] = '#';
- int j = 2;
- for(int i=0; i<len; i++)
- s_new[j++] = s[i], s_new[j++] = '#';
- s_new[j++] = '\0';
- return j;
- }
- int manacher()
- {
- int len = init();
- int max_len = -1;
- int id, mx = 0;
- for(int i=1; i<len; i++)
- {
- if(i <mx)
- p[i] = min(p[2*id - i], mx - i);
- else
- p[i] = 1;
- while(s_new[i-p[i]] == s_new[i+p[i]])
- p[i]++;
- if(mx < i+p[i])
- {
- mx = i+p[i];
- id = i;
- }
- if(max_len < p[i] - 1)
- max_len = p[i] - 1, tmp = i;
- }
- return max_len;
- }
- char c;
- int main()
- {
- while(~scanf("%c%s", &c, s))
- {
- getchar();
- int max_len = manacher();
- if(max_len < 2)
- printf("No solution!\n");
- else
- {
- int a = (tmp-p[tmp])/2, b = (tmp-p[tmp])/2+p[tmp]-2;
- printf("%d %d\n", a, b);
- for(int i=a; i<=b; i++)
- {
- if(s[i]>= c)
- printf("%c", s[i] - c + 'a');
- else
- printf("%c", 'z' - c + s[i] + 1);
- }
- printf("\n");
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2729620.html