CODE[VS]1372DNA

Description

为了进一步分析外星生物，专家们决定对 DNA 进行切割。
限制性核酸内切酶是基因工程中的重要的工具酶。它会识别一段碱基序列（说白了
就是只包含 ATGC 的序列）并且切割开。EcoRI 是某种限制酶的名称，它识别有某
种特性的 DNA序列，即 DNA序列双链反向排列相同的。（双链对应位碱基对要
满足碱基互补配对原则）
比如识别序列为 G A A T T C
互补链序列为 C T T A A G
第一条链从左读和第二条链从右读的是一样的。
专家们想知道某一段 DNA的序列中，具有这种特性的 DNA子序列（连续）最长
是多少，可限于智商，他们无法做出判断……于是，他们想到了你。

Input

第一行，一个整数n，表示 DNA序列的长度。
第二行，一个字符串，表示 DNA 序列的某一条链的碱基序列。

Output

输出只有一个数，为题目所求的最长特征 DNA 序列的长度。

Sample Input

7
GAATTCA

Sample Output

HINT

n≤ 50000

题解：

用Manacher算法求最长回文串，只不过回文的条件变为对称互补，而不是对称相等。

代码：

 uses math;

 var

   i,j,k,l,n,m,ans:longint;

   a,b:array[..]of longint;

   ch:char;

 begin

   readln(n);

   for i:= to n do

   begin

     inc(m); a[m]:=; inc(m); read(ch);

     case ch of

       'G':a[m]:=-;

       'C':a[m]:=;

       'A':a[m]:=;

       'T':a[m]:=-;

     end;

   end;

   inc(m); a[m]:=; a[m+]:=maxlongint div ;

   a[]:=maxlongint div ;

   k:=; l:=; b[]:=; ans:=;

   for i:= to m do

   if i mod = then

   begin

     if l>=i then

     b[i]:=min(b[*k-i],l-i+)else b[i]:=;

     while true do

     begin

       if a[i+b[i]]+a[i-b[i]]= then inc(b[i])

       else break;

     end;

     if b[i]>ans then ans:=b[i];

     if b[i]+i->l then begin l:=b[i]+i-; k:=i; end;

   end;

   writeln((ans div )*);

 end.

巴特西