1811. Longest Common Substring

Problem code: LCS

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

后缀自动机SAM的模板题。

重新搞一遍SAM

 /* ***********************************************

 Author        :kuangbin

 Created Time  :2013-9-8 23:27:46

 File Name     :F:\2013ACM练习\专题学习\后缀自动机\new\SPOJ_LCS.cpp

 ************************************************ */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 #include <time.h>

 using namespace std;

 const int CHAR = ;

 const int MAXN = ;

 struct SAM_Node

 {

     SAM_Node *fa, *next[CHAR];

     int len;

     int id, pos;

     SAM_Node(){}

     SAM_Node(int _len)

     {

         fa = ;

         len = _len;

         memset(next,,sizeof(next));

     }

 };

 SAM_Node SAM_node[MAXN*], *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 = ;

     SAM_root = SAM_last = newSAM_Node();

     SAM_node[].pos = ;

 }

 void SAM_add(int x,int len)

 {

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

     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 + )

     {

         np->fa = q;

         return;

     }

     SAM_Node *nq = newSAM_Node(q);

     nq->len = p->len + ;

     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 = ;i < len;i++)

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

 }

 char str1[MAXN], str2[MAXN];

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     while(scanf("%s%s",str1,str2) == )

     {

         SAM_build(str1);

         int len = strlen(str2);

         SAM_Node *tmp = SAM_root;

         int ans = ;

         int t = ;

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

         {

             if(tmp->next[str2[i]-'a'])

             {

                 tmp = tmp->next[str2[i]-'a'];

                 t++;

             }

             else

             {

                 while(tmp && !tmp->next[str2[i]-'a'])

                     tmp = tmp->fa;

                 if(tmp == NULL)

                 {

                     tmp = SAM_root;

                     t = ;

                 }

                 else

                 {

                     t = tmp->len + ;

                     tmp = tmp->next[str2[i]-'a'];

                 }

             }

             ans = max(ans,t);

         }

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

     }

     return ;

 }

巴特西

SPOJ 1811. Longest Common Substring （LCS，两个字符串的最长公共子串，后缀自动机SAM）

1811. Longest Common Substring

Problem code: LCS

Input

Output

Example

最新文章

热门文章

巴特西

SPOJ 1811. Longest Common Substring （LCS，两个字符串的最长公共子串， 后缀自动机SAM）

1811. Longest Common Substring

Problem code: LCS

Input

Output

Example

最新文章

热门文章

SPOJ 1811. Longest Common Substring （LCS，两个字符串的最长公共子串，后缀自动机SAM）