疯子的算法总结(七) 字符串算法之 manacher 算法 O(N)解决回文串

2020-10-28 09:35:28 浏览数 (1)

有点像DP的思想,写写就会做。

代码语言:javascript复制
#include<bits/stdc  .h>
using namespace std;
const int maxn=1e7 5;
char a[maxn];
char s[2*maxn];
int len[maxn*2];
int manachar(char *p)
{
    int le=strlen(p);
    for(int i=0;i<le;i  )
    {
        s[i*2 2]=p[i];
        s[i*2 1]=' ';
        //cout<<s[i*2 1]<<s[i*2 2];
    }
    s[0]='^',s[le*2 1]=' ';//选取不可能出现的字符即可。
    //预处理字符串成为一个奇数串;
    int Max=0,pos=0,ans=0;
    le=2*le 1;
    for(int i=1;i<=le;i  )
    {
        if(Max>i)
        {
            len[i]=min(len[2*pos-i],Max-i);
        }
        else  len[i]=1;
        while(s[i-len[i]]==s[i len[i]])len[i]  ;
        ans =max(len[i],ans);
        if(i len[i]>Max)
        {
            Max=len[i] i;
            pos=i;
        }
    }
    return ans-1;
}
int main()
{
    int cnt=0;
    while(~scanf(" %s",a)){
        if(a[0]=='E')break;
        printf("Case %d: %dn",  cnt,manachar(a));
        memset(a,0,sizeof(a));
    }
    return 0;
}
/*
                                                                                                                            
                                                                     ..ii7vJJuJ1juJJYL7r::.                                                           
                                                                :71XPKK5IU1JjssLYLJYJJUU5SKSX1Li.                                                     
                                                           .r1KPX2Yv77r7r7r777r7r7r7r7r7r7777sJ25XUJi.                                                
                                                        :sPPXY7r7r7r77LrvL7r7r7r7r7r7r7r7r7r7r7777vYUSKJr.              .                             
                                     :7ISKSX5Ur      :1bKu7777r7r7777ULr7us7777777r7r7r7r7r77777r7r77v7s2K27.      :vI5K5KSILi                        
                                   rS51v7777vLXg   vbqu7777r777777777rrr7r7r777r7r777r777r7r777r7r7r777r77L1qUi  .Equvv777v7u2q1i                     
                                 .5577777v77r7iXSvb577r7r7r7r7777777717rLjr7r77777777777r777r777r7r7r7r7r7777L5SLgv77777r7r7777YIXi                   
                                .qs777vu2j1Jrr2XXYrr7r77777r7r7r77v11JUJ1U1r7r7r77777r7r777r7777777r7r77777r7r7rBvr77r7r777r77777vX2                  
                                KY777vIi   :dP1ri7r777r777777777rvs.  7r  .2r7r7777777r7r7777777r777r77777r7r7rvZrr7rrv22UL777r7r77UK                 
                               rX77r72.    sbrrr7r777r77777r7r7r7ss   7i   S7r7r777r77777r77777777777777777r7r77vr7r7u1:::YSJr777777US                
                               qv77775   rEuirr7r7r7777777r7r7r7r7sJvUsJsuuvr7r7r7r7r7r77777777777r7r7r7r777r7r7r7777d     .1Ur7r777rq7               
                               Evr777L7rPq7r7r777r77777r7rrrrirvju2IXUII5II1u7v77r7rrr7r777r777r7777777r777r7r777r7r7S.      Yur7r7777D               
                               sP7r7riXQYrr77777r7r777r7vuuJjddY77rriiiiiririEI15KuX2UL7rrr7r777r7r77777r77777r77777rv5L.    jJ7r7r7rrEi              
                                2b2vrKPirr7r7r7r7r7rLuSIur.:SdY              Iv.sL :i7JISIJrrr7r7r7r777r7r7r7777777r777sSJJLIs7r77777LR               
                                 .irgIirr777r7rriv1X17:.  :qiP ............. 5r.rU .   ..:Lg117rr777777777r77777r7r777r77vvL77rrrr7sSd.               
                                   iXi7r777r7r7vP5r.     UZ.vv ............. S.  I .....  u7:YRJIvrr7r7r7r7r7r777777777r7r777r77YY1Ji                 
                                  vZi7r77777rU57g. ... :gS  X............... P:  q ..... ib:i:E::IXjr7r7r7r7r7r777r777r777777S2IUg                    
                                 7gr777777rLbL iv ... vRr  .P .............. P.  X..... .grr. iP  :JP17r7r7r777r777r7r7r7r7r7rrirYb                   
          :                     :Qr7r777rr5q. .Z .. .qX.   jv .............. E   K .... Pui.   17   .Jq2r7r7r777r7777777r7r7r7r7rrug                  
          B.i:                  Q777777rvbL  iBr   rQ7     P:................b   2 ... UXi.     g.... .LPjrr7r777r7r7r7777777r7r7rr1D                 
         iXBvL                 gY7r7r7r1d:  jPS  :bK...i.  E............... vU .:d::. sKi.      v2 .... .uKYr7r777r7r7r777r777r777772b                
          i7di:s:             Yqr77r7rKX. .P1:v :Pr     . .K .............. E:. :S...Sgr.   .    D....... :IXr7r77777r777r77777r7r77rXI               
             ..  r.           g7r7r7rEs  :Dv :::7         .S ............. iX   .L  2q:.         iK ....7:  rPYrr777r77777r7r7r777r7rrd7              
               vrSM.         U2r7r7rE7  iZ:  rri    .     :j ............. P:   r:.K1             P:... J:.. .S5rr77777r777r777r777r7r7D.             
              E1             Dr7r7rP7  i5    u.        .  :Y P:...........iK    7rIi              .E .. 1:...  Lq7r7r7r7r7777777r7r7r7rJb             
              .iv7          jU7r7rI2  i1    ..        .   :rr77 ......... D    .Y.            .    57 . X...... rPvr7r7777777r7r7r7r7r7rP7            
                            b777rLqi :j              .    .Iv X ........ 17              .         .Z ..q....... :qLr77777r7r7r777r7r7r7rM            
                           7Sr7rrK7:.L          .   .      g. E:....... iX              . . . . .   Pr .d ....... :Pvr7r77777r777r777r77712           
           7               Zr7r7jL::7.                     P  rS ......:P        .     .            :E :q ........ :P7r7777777r7r7r7r7r77rZ.          
          :B7:7.          vX7r7rP.rr.                      :   E:.....:I    .     . .       .        q.iJ ......... iP7r7r7r7r7r777777777r1I          
          .Qq:r7          Evr7rLI J.          .r7.             :P ...rL                .   .   .     vrr:........... L5rr77777r7r77777r7r7rD          
            XYir         :Er7rrJS..         vBBBBB.   .     .   Jr..7i              .       .        :PL............. qY7r777r7r7777777r77711         
             .::   .7    1I7r7rXP  .......  vBBQKi   . . .       Lir.      :BBBgv                .   :X: ............ .Er77777r777r7r7777777E         
                  :12    USr7rJ2  .........                       :        :BBBBBg                   :I .............. vUr777r7r777r77777r7rPi        
                 g:      :grrLP. .::::.:.:...           .:     .             .i7v.  ........ .       :1 .............. :gir777r777r77777r7r7LX        
                 K7v.     Purg: :ii:::r::::.... .               .   . .           ......:........    :s .............. vB7rr777r7r777r777r7r7d        
                           DPJ ii:i::r::::::.... . . . . . . . . . .         ......:::::.:i:.:....   r7............... EQS:7r7r7r77777777777rP:       
                           .B.i::r::r.:ri.:.:.. . .         . . .   .     . .....:r::::::ri.:::....  si ............. .QPEir7r7777777r7r777r7UY       
                           .U ..::ir.:r:.:.:....           . . . .     .:. ....::r::r:.:ri.i::::::.. X:.............. rBIM7rr777r7r7r7r7r7777LX       
                           2i ..::i.:::::i7vi..    :ii.               ::. ....:ri..ii.:ri.:r:::::.:. P............... bESDui777r7r7r7r7r7r7777d       
                           d. ...:.:::::.i7r..   :i: i7   ..         ri    ...ii.::7.:ri.:r:.:::::. .P ............. .QKIg1ir777r7r777r77777r7P.      
              .:iii.       b  ........... .     :.   .r i7iu:.7:.ii.ir    ......::i::ri.:ii.:::::.. 7U ............. 7BISD2i77777r7r7r7r777r7rb.      
           :uqKPXXSPqI:    d   . ....... .     .      :i.   :: ::. .K      ......:.:::::::::::::... u7 ............. ZdS2Rvr777777r7r777777777b.      
          uZIsJLsvYLs1ZK.  2:                                      .r       . ....:.:.:.:::::.....  P:............. :BXIPEir7r77777777777r777rE       
         :QLvYvLvLvLvsLMv  :5            .   .     .               i.          . ...............    P.............. UR55gsi777777777r7r7r777rLK       
         LPsvvYvLvLvYvI:.   Z.    .     .      ru   .     . . .    i.                 ... . .      :K ............  BXSPbirr777r777777777r7r72L       
         2uJJvvYvLvYvLU:.:   g     .   .       .:              .   i.                              Yv ............ sQSqgrrr7r7r7r7r777r7r7r7rZ.       
         1MsUjYvYvYvvrv2j.   .Z.                            .      .i      .:.  :rY7r.             X:............ .QqKg7rr7r7r777r777r77777r12        
          QBPvvLvLvvYIvv12s.   Pi      .           . .   .     .    ..   sPPqK5SXS25SM2      .     P ............ 2BdZ7ir7r7r777r77777r7r777Z         
           :P7vvLvL7UgD17YKP.   YU.       . .                     .     gPJvLvsLLvvsL7Qi  . .     7J............ :Bb1iir7r7r7r7r7777777r7r7Pr         
            gLvYvYvv7EEdvvLIZ    .YX.            . .                   KSv7vvv7LLL7YI712          K:............ M1rirr7r777r7r777r7r7r7rrU5          
            gKJLY7vrJDZPJ7Yuq      qLuv:                            .:52v71ZZL7vY7rLQquI         .S ........... K2ir7r7r777r777r777r77777JE           
             jKSLsr7rsJY7LvIs      7:.ivssri..                    .IXXJLv7qQgX7v77vEEZ57        .5. .......... 7drr7r7r777r7r777r7777777YZ            
               rKIZPqu77YvYYd       U . ::igKSX21YL7r:..         :MuYLYvY7LUKJvvvUgEPS1  .i72qgQBr uR ....... :g7r777777777r777r77777r7sZ             
                2QgDd57LvYvvZi      r7..r .57777LuuXPRQBQBQBPj1I5QvYvL7Lvv77r7vL7jussPbEBBBBQRZR5 jEb. ..... .dYr7r777r7r7r777r777r777jE              
                 .vKSvsLYLL7b.       7::i  2771XXSX2UYLvYYJSv7Krq2777rYvLvLvLvLvL77ruj1UUJjYY77L:uji1r ..... 52r7r777r777r7r7r7r7r7r7IP               
                    YPKPXSUqB.        iv.  ES5r.   ..ivuuuYIPJUjSJ7ssURU7LvLvLvYvL72JiiriiiriirjYvr7v2 .... vPr777r7777777r7r777r7rrUv                
                      ...iYrsr         :  jq:           ..:::rsJd57PMgEYvvv7vvLvL7vgvi7r7r7r7iX1rr7r7P.... iZr7r77777r77777r777r7irE:                 
                             .vi::..   .ii.                      PYLLJ77v7r77v7Lv2DdSXLrr7r777vrr7r7rbi . .E7777r777r777r7r7r7rriLPBi                 
                          i   v   ..::i.     .                   iX7v7v7vLSbgqJSbS.  iqdUrrr7r7r7r77r2s   Pv7r777r777777777r7rr7XbPDP                 
                          .RbQQi .          r.                   .ZUYv7vvDQggRJi  .    :KEurr7r7r777rJu  5Jrr7r7r777r77777777rrdPX5PB                 
                           jRPQP .:::.. :rYDU                   .:sJPP2u25PXU.   r:      iSPvi7r7r7r772 Yjrr77777r77777r77777isbKI5SB:                
                            .:.        .PuLd                   .:    sRqJi.     s.        :rP5i7r777rrJLJ77777r777777777r777r7rbqXISgX                
                                       ILrq7                   .      :   ..::iJ      i   ::.2Pr7r777rLsr77r7r7r7777777r7r7r7rr7PqXIqB                
                                     .Ss77Z                    27:....i      ..     :r.    r:.Ydr7r777r7r777r7r77777r7r777r777rirPqKSRX               
                                    iKLr7jI                  7PPbEBBi .:i::.      :7:      :r:.vdr7r7r7r777r7r7r7r7r77777r7r777rrrXPKXB.              
                                   1S777ib:                 LB1JYJR1     ..:irii:7i        .ri:.jKi7r7r7r7777777r7r77777r777r7r7rri2PPZQ              
                                  P17r7iYM                  .5PSqKr           ..:           ii::.XUr7r7r7r7r777r7r777r7r77777r777rriYqPB7             
                                .ZL7rriJB1                                                  :r::.:d7r7r77777r7r7r777r777r777r7r7r777irKMQ             
                                gv7rriIZB                                                   :r:::.7qrr7r7r7r7r7r77777r777r7r77777r777irXBi            
                               dJ7rrrKbBs                                .                  .r::::.Ks7r777r777r77777r7777777r7777777r7irMg            
                              rErrrrPPZS                               .i                   .i::::.:bi7r777r777r7777777r77777r7r777r7r7iuB            
                              EsrriqqKg:                             :vi                     r:i:::.Ijr7r7r7r7r7r7r777r7r7r777r7r7r777rrrB.           
                              Dr7iudPdBBv.                        :7Kj.                     .r:::::.rPrr777777777r777777777r7r7r7r7r7r7rrR:           
                           ::vPrr7bgQD7iivvvi:.                :rISs.                       .r::::::.Kv7r7r7r7r777r7r777r777777777r7r7r7rE:           
                      .:rvsv7rqrruQ2:       ...           ..rjX5Ji                          .i::i:::.v5r7777777777777r777r77777r7r7r777rrPi           
                   .ivYL7rrrii27i1:                     ...:i:.                             :i::::::::Krr7r7777777r7r77777r7777777r777r7iKS:.         
                 :vYvrrrririiiYZZESDQqi                                                     r:::i::::.Sv7r7r77777r7777777r7r7r777777777riquiYvi       
               :vYrririririrYji.:vPXUZBB.                                                  .ri:::::::.vjr7r777r777r7r77777r7r7r777r77777rMrii7vs:     
              7L7rrirrL7rrjv:      XKUSQBr                                                 :r:::::::: vJrr7r7r77777r7r7r77777r7r7r7r777iub:irirrYv    
             7Lririr7  rjr    .:r7rdRd5SKBS.                                               r::::::...vQvr7777777r77777r7777777r7r777r7rrgr:ririrrLv   
             s7iririru    .iLJuL7ii:LqDPKKgQ5.                                            iii:::..:vbQdi7r77777r77777r777r777r7r7r7r7ivEL:iiririrru   
             7vrrririvs.rsYvrriririi::7XdDPdgBPr                                         :r::..:rSZgZDrrr7r777r7r77777r7777777r7r7rr7Sq7:iiriririvv   
              Yv7rriri7Y7iiiririririii::iLKEgDQBBbji:.       .isqK7                     .i:..iUbgdPPb7ir7r7r7r7r777777777r7r7r7rr7u5KYi:iiririrrLY.   
               rYvrririiiriririririririi:::i7uSbDQBBBBBBMRBBRQQBBQBB2                   :.:JqgdPKdPUirr7777777r777r7r7r7rrrrrvsI5Ssr::iiirirrr7Jr     
                 iYv7rriririririririririiii::.::ii7L1IqKBBU     iS2PBBI.               :vSgZbXPPb27irr7r777r7r7rrrrr7rvvYJ22S217r:::iirirrr7Lvr.      
                   :rYLvrrrririririririririririiiiii.:rj7       .PDEbgQBQgjr.        .2ggDKPPdXU7ii7r7rrrrrrr7vYJUUI25UUJs7rii::iiirrrr77Yv7:         
                      .i7LY77rririririririririri7: rjLi    .rvJv7:::iir71KQBBBRXY:..IQQdbPP517riiirr7r7vsJI2522JY77rii::::i:iirirrrrvLY7i.            
                          .irvvYv7rrrririririririU  .   :7Yjvririiii:i:::::r71qRQBBBQEXIsvri:irvvjjI2IU1YY7rii:::i:iiiiririrr77vvYv7i:                
                               .:ivvYvY7vrrrrrriivY .isJsrriririririiiriiii:::::irvJ1YsvLvJJ1UUjjv7rrii:i:i:iiririrrrr77vvYvL7r:.                     
                                     ..:r77LvYvLv7JIjYrrrrrririrrriririririririi:i::::iirrrriiii:iiiirirrrr7r77vvLLLvv7ri:..                          
                                             ...iirr77YvYLYvLvL7v7v7vr7777777r7r7r7r7r7rrrrr7r77v7LvYvsLYvv77ri::..                                   
                                                         ....::::iirrrr7r777777v77777777rrrriiii::.....                                              

                                                         */
dp

0 人点赞