POJ3974 回文串。EXKMP模板和马拉车算法模板

时间：2023-01-03 17:06:51

题目就是求一个串的最长回文子串，


马拉车算法就不介绍了。。我博客里曾经有过……而且我自己倒是理解透彻不搞了。。


这次是KMP求最长回文子串。


扩展KMP。


求最长回文子串与最长重复子串。

长沙雅礼中学 何林


记录一篇论文叫……


然后就行了……看完就发现分治很神奇。

然后……程序超级慢，毕竟比马拉车多个log。跑了10秒，别人1秒内……多个log太慢了


顺便，获得扩展KMP模板


//得到扩展KMP的next数组。next[i]，T从i开始的串，和pattern的前缀公共长度
//一般对不求extend[i]的数组进行使用。
template<typename T>
void get_extand_next(T pattern[], int lenP, int next[])
{
int a(0);
next[0] = lenP;
for (; a != lenP && pattern[a] == pattern[a + 1]; ++ a);
next[1] = a;
a = 1;
for (int k = 2; k < lenP; ++ k)
{
int p = a + next[a] - 1, L = next[k - a];
//p是最远匹配下标，L是当前串
if (k-1+L >= p)
{
int j = (p - k + 1) > 0 ? p - k + 1 : 0;
while (k + j < lenP && pattern[k + j] == pattern[j])j++;
next[k] = j;
a = k;
}
else next[k] = L;
}
}


template<typename T>
void get_extend(T text[], int lenT, T pattern[], int lenP, int next[], int extend[], bool flag = 0)//flag表示是否已经得到next数组了,0表示否
//extend[i]表示text[i..lenT-1]和pattern[0..lenP-1]串的公共前缀
{
if (!flag)get_extand_next(pattern, lenP, next);
int a = 0;
int len = min(lenT, lenP);//两个串取短
while (a < len && text[a] == pattern[a])a++;
extend[0] = a;
a = 0;
for (int k = 1; k != lenT; k ++ )
{
int p = a + extend[a] - 1, L = next[k - a];
if (k - 1 + L >= p)
{
int j = (p - k + 1) > 0 ? p - k + 1 : 0;
while (k + j < lenT && j < lenP && text[k + j] == pattern[j])j++;
extend[k] = j;
a = k;
}
else extend[k] = L;
}
}

ac code 

/*
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <tr1/unordered_map>
#include <ctime>
using std::tr1::unordered_map;
*/

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;

/*
   using std::sort;
   using std::bitset;
   using std::max;
   using std::cout;
   using std::stack;
   using std::cin;
   using std::endl;
   using std::swap;
   using std::pair;
   using std::vector;
   using std::set;
   using std::map;
   using std::multiset;
   using std::queue;
   using std::greater;
   using std::string;
   using std::priority_queue;
   using std::max_element;
   using std::min_element;

   using __gnu_pbds::pairing_heap_tag;
   __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> heap;
#define Hash unordered_map
*/
#define pr(x) cout<<#x<<" = "<<x<<" "
#define prln(x)    cout<<#x<<" = "<<x<<endl

#define lson o*2, L, M
#define rson o*2+1, M + 1,R

//const int maxn = 210000;
const int maxn = 1000100;





//得到扩展KMP的next数组。next[i]，T从i开始的串，和pattern的前缀公共长度
//一般对不求extend[i]的数组进行使用。
template<typename T>
void get_extand_next(T pattern[], int lenP, int next[])
{
int a(0);
next[0] = lenP;
for (; a != lenP && pattern[a] == pattern[a + 1]; ++ a);
next[1] = a;
a = 1;
for (int k = 2; k < lenP; ++ k)
{
int p = a + next[a] - 1, L = next[k - a];
//p是最远匹配下标，L是当前串
if (k-1+L >= p)
{
int j = (p - k + 1) > 0 ? p - k + 1 : 0;
while (k + j < lenP && pattern[k + j] == pattern[j])j++;
next[k] = j;
a = k;
}
else next[k] = L;
}
}


template<typename T>
void get_extend(T text[], int lenT, T pattern[], int lenP, int next[], int extend[], bool flag = 0)//flag表示是否已经得到next数组了,0表示否
//extend[i]表示text[i..lenT-1]和pattern[0..lenP-1]串的公共前缀
{
if (!flag)get_extand_next(pattern, lenP, next);
int a = 0;
int len = min(lenT, lenP);//两个串取短
while (a < len && text[a] == pattern[a])a++;
extend[0] = a;
a = 0;
for (int k = 1; k != lenT; k ++ )
{
int p = a + extend[a] - 1, L = next[k - a];
if (k - 1 + L >= p)
{
int j = (p - k + 1) > 0 ? p - k + 1 : 0;
while (k + j < lenT && j < lenP && text[k + j] == pattern[j])j++;
extend[k] = j;
a = k;
}
else extend[k] = L;
}
}

char input[maxn];
int ans;
int suf_left[maxn], suf_right[maxn];
int nxt[maxn], extend[maxn];
char pattern[maxn], text[maxn];

void cal(char s[], int len, int M)//分界线为M-1和M之间
{
int lenP = len - M;
int lenT = M;
//for (int i = 0; i != len; ++ i)cout<<s[i];cout<<endl;
//先求出左边串为母串，和左边串的逆为子串的EXKMP
for (int i = 0; i < M; ++ i)text[i] = s[i];//text[i] 为s[0..M-1]
for (int i = 0; i < M; ++ i)pattern[i] = s[M - i - 1];//pattern为s[0..M-1]的逆
get_extend(text, lenT, pattern, lenP, nxt, extend);
for (int i = 0; i < M; ++ i)suf_left[i] = extend[i];
//suf_left[i]表示,s[i]为起点往右，和s[M-1]为起点往左，有多少个相同的串

for (int i = 0; i < M; ++ i)text[i] = s[M - i - 1];//text[i]为s[0..M-1]的逆
for (int i = M; i < len; ++ i)pattern[i - M] = s[i];

get_extend(text, lenT, pattern, lenP, nxt, extend);
for (int i = 0; i < M; ++ i)suf_right[i] = extend[M - 1 - i];
for (int i = 1; i < M; ++ i)
{
if (suf_left[i] * 2 >=  M - i)//存在
{
int tmp = M - i + suf_right[i-1] * 2;
if (tmp > ans)ans = tmp;
}
}
int tmp = suf_right[M - 1] * 2;
if (tmp > ans)ans = tmp;
}

void solve(char s[], int len)
{
if (len == 1)
{
if (ans < 1)ans = 1;//一个元素答案一定为1
return;
}
int M = len / 2;

solve(s, M);//s[0]...s[M-1]一共 M个元素 
solve(s + M, len - M);//s[M]...s[len - 1] 一共len-M个元素
cal(s, len, M);
for (int i = 0; i < len/2; ++ i)swap(s[i], s[len-i-1]);
if (len%2==1)M++;
cal(s, len, M);
for (int i = 0; i < len/2; ++ i)swap(s[i], s[len-i-1]);
}

int main()
{
int T=0;
while (~scanf("%s", input))
{
if (input[0]=='E')break;
int len = strlen(input);
ans = 1;
solve(input, len);
printf("Case %d: ", ++T);
printf("%d\n", ans);
}

return 0;
}



马拉车模板：

//获得manacher算法数组
//给定一个text模板串，下标从0开始。长度为len，输出一个malache数组。同时需要提供一个运算辅助数组str，其类型与text相同
//算法流程：首先给字符首插入未出现的字符，第奇数个字符开始插入#等相同的，并且原字符串没有出现的字符。
//然后在第偶数个位置，按顺序插入原串。比如abbacabba会变为^#a#b#b#a#c#a#b#b#a* 这样的串，首尾都是未出现的串。这样是为了程序避免越界，为了程序好写。
//然后会返回一个manacher数组，表示对于从^#a#b#b#a#c#a#b#b#a*这样的字符串中，每个下标为中心，向左右扩展，能得到的最长回文串的长度。
//实质上，是在原串的(pos-malache[pos]+2)/2-1为左端点，长度为malache[pos]-1的回文串

#include <typeinfo>
template<typename T>
void manacher(T text[], int len, int malache[], T str[])  
{  
T inf, space;
if (typeid(T).name() == typeid(char).name())
{
inf= -128;
space = 2 - 127;
}
if (typeid(T).name() == typeid(int).name())
{
inf= - 0x3f3f3f3f;
space = 2 -0x3f3f3f3f;
}
int l = 0;
str[l++] = inf;
str[l++] = space;
for (int i = 0; i < len; ++ i)
{
str[l++] = text[i];
str[l++] = space;
}
str[l] = inf + 1;
int mx=0, id=0;//mx:最远匹配距离,id:最远距离对应的坐标的下标
for (int i = 0; i < l; ++ i)
{
malache[i] = mx > i ? min(malache[2 * id - i], mx - i) : 1;
while (str[i + malache[i]] == str[i - malache[i]])malache[i] ++ ;
if (i + malache[i] > mx)
{
mx = i + malache[i];
id = i;
}
}

}

ac code 

/*
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <tr1/unordered_map>
#include <ctime>
using std::tr1::unordered_map;
*/

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;

/*
   using std::sort;
   using std::bitset;
   using std::max;
   using std::cout;
   using std::stack;
   using std::cin;
   using std::endl;
   using std::swap;
   using std::pair;
   using std::vector;
   using std::set;
   using std::map;
   using std::multiset;
   using std::queue;
   using std::greater;
   using std::string;
   using std::priority_queue;
   using std::max_element;
   using std::min_element;

   using __gnu_pbds::pairing_heap_tag;
   __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> heap;
#define Hash unordered_map
*/
#define pr(x) cout<<#x<<" = "<<x<<" "
#define prln(x)    cout<<#x<<" = "<<x<<endl

#define lson o*2, L, M
#define rson o*2+1, M + 1,R

//const int maxn = 210000;
const int maxn = 1000100;

//对于text[]，返回一个out[],out[i]，表示从i开始，可以向右多远是合法的




#include <typeinfo>
template<typename T>
void manacher(T text[], int len, int malache[], T str[])  
{  
T inf, space;
if (typeid(T).name() == typeid(char).name())
{
inf= -128;
space = 2 - 127;
}
if (typeid(T).name() == typeid(int).name())
{
inf= - 0x3f3f3f3f;
space = 2 -0x3f3f3f3f;
}
int l = 0;
str[l++] = inf;
str[l++] = space;
for (int i = 0; i < len; ++ i)
{
str[l++] = text[i];
str[l++] = space;
}
str[l] = inf + 1;
int mx=0, id=0;//mx:最远匹配距离,id:最远距离对应的坐标的下标
for (int i = 0; i < l; ++ i)
{
malache[i] = mx > i ? min(malache[2 * id - i], mx - i) : 1;
while (str[i + malache[i]] == str[i - malache[i]])malache[i] ++ ;
if (i + malache[i] > mx)
{
mx = i + malache[i];
id = i;
}
}
/*
   for (int i = 0; i <l;++i)
   cout<<i<<" ";cout<<endl;
   for (int i = 0; i <l;++i)
   cout<<str[i]<<" ";cout<<endl;
   for (int i = 0; i <l;++i)
   cout<<malache[i]<<" ";cout<<endl;
   */

}

char flag[10],input[200000 + 200];
int malache[200000 + 200];
char str[200000 + 200];

int main()
{
while (scanf(" %s %s ", flag, input) == 2)
{
char ch = flag[0];
int len = strlen(input);
for (int i = 0; i != len; ++ i)
{
input[i] = (input[i]-ch+26)%26 + 'a';
}
manacher(input, len, malache, str);
int pos=0, ans=0;
for (int i = 0; i < 2 * len + 2; i ++)
{
if (malache[i]>ans)
{
ans = malache[i];
pos = i;
}
}
ans--;
if (ans==1)
printf("No solution!\n");
else
{
if (pos%2==0)
{
//如果是偶数，则为pos/2-1为中点
//pos-malache[pos]+1为起点
//起点为 (pos-malache[pos]+1)/2-1为起点，长为malache[pos]-1
printf("%d %d\n", (pos-malache[pos]+2)/2-1, ans);
}
else
{
//如果是奇数，则说明为aa或者baab这样的回文串
//(pos-malache[pos])/2为起点，长度为malache[pos]-1
printf("%d %d\n", (pos-malache[pos]+2)/2-1, ans);
}
for (int i = (pos-malache[pos])/2; i <= (pos-malache[pos])/2 + ans - 1; ++ i)
printf("%c", input[i]);
printf("\n");
}
}
}


标签：

相关文章