51nod 1286 三段子串（树状数组+拓展kmp）

题意：

给定一个字符串S，找到另外一个字符串T，T既是S的前缀，也是S的后缀，并且在中间某个地方也出现一次，并且这三次出现不重合。求T最长的长度。

例如：S = "abababababa"，其中"aba"既是S的前缀，也是S的后缀，中间还出现了一次，并且同前缀后缀均不重合。所以输出"aba"的长度3。如果找不到一个符合条件的字符，输出0。

题解：

先对S做一次拓展kmp，求出next数组

然后其实next每一个数就对应了一个前缀匹配的情况。

比如说next[3]和next[5]都为2，就意味着前缀为2的子串可以和位置为3和位置为5的子串匹配。

然后我们按照next数组倒序来做。

对于长度为i的前缀，先判断是否存在长度为i的后缀匹配，如果存在再询问是否存在中间子串。

每次匹配的结果都插入到树状数组里面（因为如果某个位置可以匹配L的前缀，那么实际上1~L-1都能匹配）

然后询问i+1 ~ L-2i+1这个区间里有没有能匹配的子串（即中间的那个串）。

#include <iostream>

#include <cstring>

#include <vector>

using namespace std;

const int maxn = 1e6 + ;

char S[maxn];

int Next[maxn], extend[maxn];

vector<int> G[maxn];

int len;

int c[maxn*];

void Modify(int x, int s){

    for(; x <= len; x += x&(-x)) c[x] += s;

}

int Query(int y){

    if(y <= ) return ;

    int ans = ;

    for(int x = y; x; x -= x&(-x)) ans += c[x];

    return ans;

}

int query(int x, int y) { return x <= y ? Query(y) - Query(x-) : ; }

void GetNext(char *T, int *Next){

    int len = strlen(T);

    Next[] = len;

    int a, p;

    for(int i = , j = -; i < len; i++, j--){

       if(j <  || i + Next[i-a] >= p){

            if(j < ) p = i, j = ;

            while(p < len && T[p] == T[j])

                p++, j++;

            Next[i] = j;

            a = i;

       } else Next[i] = Next[i-a];

    }

}

void GetExtend(char *S, char *T, int *extend, int *Next){

    GetNext(T, Next);

    int a, p;

    int slen = strlen(S), tlen = strlen(T);

    for(int i = , j = -; i < slen; i++, j--){

        if(j <  || i + Next[i-a] >= p){

            if(j < ) p = i, j = ;

            while(p < slen && j < tlen && S[p] == T[j]) p++, j++;

            extend[i] = j;

            a = i;

        } else extend[i] = Next[i-a];

    }

}

int main()

{

    cin>>S;

    len = strlen(S);

    GetNext(S, Next);

    //for(int i = 0; i < len; i++) cout<<Next[i]<<" "; cout<<endl;

    for(int i = ; i < len; i++) G[Next[i]].push_back(i);

    int ans = ;

    for(int i = len-; i >= ; i--){

        for(auto x : G[i]) Modify(x+, );

        int n = G[i].size();

        if(n == ) continue;

        if(G[i][n-] != len-i) continue;

        if(query(i+, len-*i+)) { ans = i; break; }

    }

    cout<<ans<<endl;

    return ;

}

巴特西

51nod 1286 三段子串（树状数组+拓展kmp）

最新文章

热门文章