SPOJ 1811LCS Longest Common Substring

后缀自己主动机裸题....

Longest Common Substring

Time Limit: 2000MS

Memory Limit: Unknown

64bit IO Format: %lld & %llu

[Submit]
[Go Back] [Status]

Description

A string is finite sequence of characters over a non-empty finite set Σ.

In this problem, Σ is the set of lowercase letters.

Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.

Now your task is simple, for two given strings, find the length of the longest common substring of them.

Here common substring means a substring of two or more strings.

Input

The input contains exactly two lines, each line consists of no more than 250000 lowercase letters, representing a string.

Output

The length of the longest common substring. If such string doesn't exist, print "0" instead.

Example

Input: alsdfkjfjkdsal

fdjskalajfkdsla Output: 3

Notice: new testcases added

Source

[Submit]
[Go Back] [Status]

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int CHAR=26,maxn=251000;

struct SAM_Node

{

    SAM_Node *fa,*next[CHAR];

    int len,id,pos;

    SAM_Node(){}

    SAM_Node(int _len)

    {

        fa=0; len=_len;

        memset(next,0,sizeof(next));

    }

};

SAM_Node SAM_node[maxn*2],*SAM_root,*SAM_last;

int SAM_size;

SAM_Node *newSAM_Node(int len)

{

    SAM_node[SAM_size]=SAM_Node(len);

    SAM_node[SAM_size].id=SAM_size;

    return &SAM_node[SAM_size++];

}

SAM_Node *newSAM_Node(SAM_Node *p)

{

    SAM_node[SAM_size]=*p;

    SAM_node[SAM_size].id=SAM_size;

    return &SAM_node[SAM_size++];

}

void SAM_init()

{

    SAM_size=0;

    SAM_root=SAM_last=newSAM_Node(0);

    SAM_node[0].pos=0;

}

void SAM_add(int x,int len)

{

    SAM_Node *p=SAM_last,*np=newSAM_Node(p->len+1);

    np->pos=len;SAM_last=np;

    for(;p&&!p->next[x];p=p->fa)

        p->next[x]=np;

    if(!p)

    {

        np->fa=SAM_root;

        return ;

    }

    SAM_Node *q=p->next[x];

    if(q->len==p->len+1)

    {

        np->fa=q;

        return ;

    }

    SAM_Node *nq=newSAM_Node(q);

    nq->len=p->len+1;

    q->fa=nq; np->fa=nq;

    for(;p&&p->next[x]==q;p=p->fa)

        p->next[x]=nq;

}

void SAM_build(char *s)

{

    SAM_init();

    int len=strlen(s);

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

        SAM_add(s[i]-'a',i+1);

}

char A[maxn],B[maxn];

int main()

{

    scanf("%s%s",A,B);

    SAM_build(A);

    int m=strlen(B),ans=0,temp=0;

    SAM_Node *now=SAM_root;

    for(int i=0;i<m;i++)

    {

        int c=B[i]-'a';

        if(now->next[c])

        {

            now=now->next[c];

            temp++;

        }

        else

        {

            while(now&&!now->next[c])

                now=now->fa;

            if(now)

            {

                temp=now->len+1;

                now=now->next[c];

            }

            else

            {

                temp=0;

                now=SAM_root;

            }

        }

        ans=max(ans,temp);

    }

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

    return 0;

}

巴特西

SPOJ 1811LCS Longest Common Substring

Input

Output

Example

最新文章

热门文章