完全的未知领域，只能摸着前辈过河，于是一般时间都花在研读OI-wiki和打模板上了，模板文收获颇丰（

A – 【模板题】manacher 算法

上来就蓝题模板的含金量（

跟【主站】《试图整一个自己的模板列表》里的对应模板是一样的，以下为按照原理精注版本，不排除将模板文章里的改成减少码量+简化逻辑版本的可能性。

/******************************\
 * Manacher 算法 O(N)
 * Init: si (char si[])
 * Call: manacher(si)
 * Resu: 返回最大回文串长度
 * Comm: 用于在字符串中快速找出最大回文串
\******************************/
namespace lovelive{
    const int MAXN = 11000005;
    char si[MAXN];
    int manacher(char si[]){
        int d1[MAXN],d2[MAXN];
        int l1,r1,l2,r2,len,j,ans;
        len = strlen(si);
        l1 = 0;r1 = -1;
        l2 = 0;r2 = -1;
        ans = 0;
        for(int i=0;i<len;i++){
            //求奇数长度的回文串的Manacher算法
            //Manacher算法的核心是利用对当前边界最右侧
            //的已知回文串的已知信息进行记忆化
            if(i>r1){                   //当前在回文串外面
                d1[i]=1;                //直接使用朴素算法
                while(i-d1[i]>=0 && i+d1[i]<len && si[i-d1[i]]==si[i+d1[i]]){
                    d1[i]++;
                }
            }else{                      //当前在回文串里面
                j = l1 + r1 - i;        //搜索当前回文串的对称位置
                                        //在当前位置之前的回文串都处理完毕了
                                        //所以现在肯定在回文串的后半段
                if(i+d1[j]-1 >= r1){    //如果对称位置的回文串边界超出了当前回文串的边界
                    d1[i] = r1 - i + 1; //不能轻举妄动，因为回文串外的回文性未知
                    while(i-d1[i]>=0 && i+d1[i]<len && si[i-d1[i]]==si[i+d1[i]]){
                        d1[i]++;
                    }                   //喜闻乐见的朴素算法
                }else{
                    d1[i] = d1[j];      //没问题就直接用，没关系的
                }
            }//接下来就该记录答案了
            //无论如何请不要忘记更新边界值
            if(r1==-1 || r1<i+d1[i]-1) r1 = i+d1[i]-1, l1 = i-d1[i]+1;
            ans = max(ans,2*d1[i]-1);

            //求偶数长度的回文串的Manacher算法
            //与奇数版本基本相同，注意相关计算的更改
            //这里选择在偶数长度回文串的右中心记录值
            if(i>r2){
                d2[i] = 0;              //偶数长度回文可能不存在，初始置0
                while(i-d2[i]-1>=0 && i+d2[i]<len && si[i-d2[i]-1]==si[i+d2[i]]){
                    d2[i]++;
                }
            }else{
                j = l2 + r2 - i + 1;    // * * ! * + + * * ! *
                                        // 0 1 2 3 4 5 6 7 8 9  
                if(i+d2[j]-1 >= r2){
                    d2[i] = r2 - i + 1;
                    while(i-d2[i]-1>=0 && i+d2[i]<len && si[i-d2[i]-1]==si[i+d2[i]]){
                        d2[i]++;
                    }
                }else{
                    d2[i] = d2[j];
                }
            }
            //偶数长度回文串可能不存在
            if(d2[i] && r2<i+d2[i]-1) r2 = i+d2[i]-1, l2 = i-d2[i];
            ans = max(ans,2*d2[i]);
        }
        return ans;
    }
}

B – Palindrome

多组数据版本的A题，就不再重复代码了。

F – 【模板题】扩展 KMP（Z 函数）

为了学这个紫题扩展KMP于是把普通KMP也一道学掉了（模板在上文提到多次的模板文里了），然后发现扩展KMP的思想更像是 manacher 算法。

const int MAXN = 20000005;
char source[MAXN],target[MAXN];
LL res[MAXN*2];
namespace lovelive{
    LL ans1,ans2;
    int szs,szt;
    inline char nico(int i){
        return i<szt?target[i]:(i==szt?'#':source[i-szt-1]);
    }
    void z_func(){
        int len = szs + szt + 1, l=0, r=0;
        for(int i=1;i<len;i++){
            if(i<=r && res[i-l] < r-i+1){
                res[i] = res[i-l];
            }else{
                res[i] = max(0,r - i + 1);
                while(i+res[i]<len && nico(res[i])==nico(i+res[i])){
                    res[i]++;
                }
            }
            if(i+res[i]-1 > r) l = i, r = i+res[i]-1;

            if(i<szt) ans1 ^= (res[i]+1) * (i+1);
            if(i>szt) ans2 ^= (res[i]+1) * (i-szt);
            //cout<<i<<"\t"<<res[i]<<endl;
        }
    }
    void main(){
        scanf("%s",source);
        scanf("%s",target);
        szs = strlen(source);
        szt = strlen(target);
        ans1 = szt + 1;
        ans2 = 0;
        res[0] = 0;
        z_func();
        printf("%lld\n%lld\n",ans1,ans2);
        return;
    }
}

J – 【模板题】字典树

什么？它不是黄题，它是一道压缩蓝紫题，遇自动机就会变大变高（

namespace lovelive{
    const int MAXN = 3000005;
    char s[MAXN];
    int n,m;
    class TRIE{
        private:
            int nxt[MAXN][70],nxtc;
            int cnt[MAXN];
            inline int nico(char c){
                if(c>='0'&&c<='9')      return c-'0';
                else if(c>='a'&&c<='z') return c-'a'+10;
                else if(c>='A'&&c<='Z') return c-'A'+36;
                else                    return 66;
            }
        public:
            TRIE(){
                reset(0);
                nxtc = 0;
            }
            void reset(int pnt=0){
                cnt[pnt] = 0;
                for(int i=0;i<=66;i++){
                    nxt[pnt][i] = 0;
                }
            }
            void insert(char *s){
                int p = 0, len = strlen(s);
                for(int i=0;i<len;i++){
                    cnt[p]++;
                    if(!nxt[p][nico(s[i])]){
                        nxt[p][nico(s[i])] = ++nxtc;
                        reset(nxtc);
                    }
                    p = nxt[p][nico(s[i])];
                }
                cnt[p]++;
            }
            int count(char *s){
                int p = 0, len = strlen(s);
                for(int i=0;i<len;i++){
                    if(!nxt[p][nico(s[i])])
                        return 0;
                    p = nxt[p][nico(s[i])];
                }
                return cnt[p];
            }
    }t;

    void main(){
        scanf("%d%d",&n,&m);
        t.reset();
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            t.insert(s);
        }
        for(int i=1;i<=m;i++){
            scanf("%s",s);
            printf("%d\n",t.count(s));
        }
    }
}