Corporate Identity - HDU 2328（多串求共同子串）

题目大意：给你N（2-4000）个字符串，求出来他们的共同子串

 

分析：因为上次就说了再出现这种题就不用那种暴力的做法了，于是看了一些别的知识，也就是后缀树，把一个字符串的所有的后缀全部都加入字典树，然后用别的串去匹配，这样匹配的时候速度那是飕飕的啊，不过第一次我把前N-1个串的所有前缀搞进了字典树里面，然后想如果某个节点被访问N-1次，并且第N个串也能访问到此节点，那么这一定就是他们的共同子串了，不过总归是太天真，直接返回MLE,一细琢磨，想着最糟糕的情况也就是有8000（N）个串，每个串都不相同，并且每个串的长度是200（len），那么空间复杂度应该是 len*（len+1）/2*N*26 大约理论上最糟糕的情况就是41亿内存，不超才见鬼了呢于是又换一种想法，如果只把第一个串的所有后缀加入字典树不就行了？因为求的是共同子串，第一个串也肯定包括所有串的共同子串，这样内存开销就会降到len*（len+1）/2*26大约50w不到，比较容易接受了。

 

下面是AC代码：

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

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<stdlib.h>

using namespace std;

const int MAXN = ;

const int MAXM = ;

const int oo = 1e9+;

struct node

{

    int times;

    node *next[MAXN];

};

int BuildTrie(node *head, char s[], int x)

{

    int i, k, depth = ;

    node *P = head;

    for(i=; s[i]; i++)

    {

        k = s[i] - 'a';

        if(P->next[k] == NULL)

        {

            if(x != )

                break;

            P->next[k] = new node();

        }

        P = P->next[k];

        if(P->times +  >= x)

        {///如果此节点是本个串访问过或者上个节点访问过

            P->times = x;

            depth++;

        }

        else break;

    }

    return depth;

}

void clearTrie(node *head)

{///销毁树

    node *P = head;

    for(int i=; i<MAXN; i++)

    {

        if(P->next[i] != NULL)

            clearTrie(P->next[i]);

    }

    free(P);

}

int main()

{

    int i, j, N;

    while(scanf("%d", &N), N)

    {

        node *head = new node();

        char s[MAXM]={}, ans[MAXM]={};

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

        {

            scanf("%s", s);

            for(j=; s[j] != '\0'; j++)

                BuildTrie(head, s+j, i);

        }

        scanf("%s", s);

        int Max = ;

        for(j=; s[j] != '\0'; j++)

        {

            int len = BuildTrie(head, s+j, N);

            char p[MAXM] = {};

            strncpy(p, s+j, len);

            if(Max < len || (Max==len && strcmp(ans, p) > ))

                strcpy(ans, p), Max = len;

        }

        if(ans[] == )

            printf("IDENTITY LOST\n");

        else

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

        clearTrie(head);

    }

    return ;

}