Finding Palindromes - 猥琐的字符串（Manacher+trie）

题目大意：有 N 个字符串，所有的字符串长度不超过 200W 任意俩俩字符串可以自由组合，问组合的字符串是回文串的个数有多少个？

分析：这是一个相当猥琐的字符串处理，因为没有说单个的字符串最少多长，所以很可能会有这样的情况，200w个字符串，每个字符串长度1,或者1个串，这个串的长度是100w, 为了对付这种猥琐的方式可以用一个长为100w的字符串保存所有的串，然后用另一个数组记录每个字符串所在的区间。匹配的时候可以使用trie因为回文串是两端匹配，所以插入trie的时候可以倒着插入，不过查询的时候会出现两种情况，一种是这个字符串已经匹配完，不过他后面匹配的字符串没有完，另一种是这个字符串匹配完还有剩余长度，不管哪种情况都需要判断一下剩余的串是否是回文串，tire里面的保存后缀，匹配串保存的是前缀。

代码如下：

================================================================================================================

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

const int MAXN = 2e6+;

const int oo = 1e9+;

struct Trie

{///字典树的节点

    int next[];

    int leaf;///以这个节点为终点的叶子节点个数

    int count;///后面回文串的数量

    void Free()

    {

        leaf = count = ;

        memset(next, false, sizeof(next));

    }

}trie[MAXN];

int top;///配合字典树使用，top表示没有使用的内存

int start[MAXN], p[MAXN<<];

char MumStr[MAXN], Estr[MAXN<<];

bool suffix[MAXN];///后缀是否是回文串

bool prefix[MAXN];///前缀是否是回文串

void BuildTrie(int n)

{

    int p = ;

    for(int i=start[n+]-; i>=start[n]; i--)

    {///把字符串倒插进去

        int k = MumStr[i] - 'a';

        trie[p].count += prefix[i];

        if(trie[p].next[k] == )

        {

            trie[p].next[k] = ++top;

            trie[top].Free();

        }

        p = trie[p].next[k];

    }

    trie[p].leaf += ;

}

void Manacher(int n)

{

    int i, id=, len=;

    Estr[] = '$';

    for(i=start[n]; i<start[n+]; i++)

    {

        Estr[len++] = '#';

        Estr[len++] = MumStr[i];

        suffix[i] = false;

        prefix[i] = false;

    }

    Estr[len] = '#';

    Estr[len+] = ;

    for(i=; i<len; i++)

    {

        p[i] = ;

        if(p[id]+id > i)

            p[i] = min(p[id*-i], p[id]+id-i);

        while(Estr[ i+p[i] ] == Estr[ i-p[i] ])

            p[i]++;

        if(p[id]+id < p[i]+i)

            id = i;

        if(p[i] == i)

            prefix[ start[n]+p[i]- ] = true;

        if(p[i]+i- == len)

            suffix[ start[n+]-p[i]+ ] = true;

    }

}

int Query(int n)

{

    int i, p=, sum = ;

    for(i=start[n]; i<start[n+]; i++)

    {

        int k = MumStr[i] - 'a';

        if(trie[p].next[k] == )

            break;

        p = trie[p].next[k];

        if(suffix[i+] || i==start[n+]-)

            sum += trie[p].leaf;

    }

    if(i == start[n+])

        sum += trie[p].count;

    return sum;

}

int main()

{

    int N;

    while(scanf("%d", &N) != EOF)

    {

        int i, len;

        top = ;

        trie[].Free();

        for(i=; i<=N; i++)

        {

            scanf("%d%s", &len, MumStr+start[i]);

            start[i+] = start[i] + len;

            Manacher(i);

            BuildTrie(i);

        }

        long long ans = ;

        for(i=; i<=N; i++)

            ans += Query(i);

        printf("%lld\n", ans);

    }

    return ;

}

/**

2

3 abc

4 acba

*/

巴特西

Finding Palindromes - 猥琐的字符串（Manacher+trie）

最新文章

热门文章