SPOJ LCS Longest Common Substring

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

后缀自动机

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 300005;
char s[maxn];

class SAM
{
  const static int maxn = 500005;   //节点个数  
  const static int size = 26;     //字符的范围  
  const static char base = 'a';     //字符的基准  

  class node
  {
  public:
    node *fa, *next[size];
    int len, cnt;
    node* clear(int x)
    {
      fa = 0; len = x;
      cnt = 0;
      memset(next, 0, sizeof(next));
      return this;
    }
  }nd[maxn];                      //节点的设置  

  node *root, *last;              //根节点,上一个节点  
  int tot;                        //总节点数  
public:
  void clear()
  {
    last = root = &nd[tot = 0];
    nd[0].clear(0);
  }                               //初始化  
  void insert(char ch)
  {
    node *p = last, *np = nd[++tot].clear(p->len + 1);
    last = np;
    int x = ch - base;
    while (p&&p->next[x] == 0) p->next[x] = np, p = p->fa;
    if (p == 0) { np->fa = root; return; }

    node* q = p->next[x];
    if (p->len + 1 == q->len) { np->fa = q; return; }

    node *nq = nd[++tot].clear(p->len + 1);
    for (int i = 0; i < size; i++)
      if (q->next[i]) nq->next[i] = q->next[i];
    nq->fa = q->fa;
    q->fa = np->fa = nq;
    while (p &&p->next[x] == q) p->next[x] = nq, p = p->fa;
  }                               //插入操作  

  void find(char *ch)
  {
    node *s = root;
    int maxlen = 0, ans = 0;
    for (int i = 0; ch[i]; i++)
    {
      int x = ch[i] - base;
      if (s->next[x]) 
      {
        s = s->next[x];
        s->cnt = max(s->cnt, ++maxlen);
      }
      else
      {
        while (s&&!s->next[x]) s = s->fa;
        if (s == 0) s = root,maxlen = 0;
        else  maxlen = s->len + 1, s = s->next[x];
      }
      ans = max(ans, maxlen);
    }
    printf("%d\n", ans);
  }
}sam;

int main()
{
  while (~scanf("%s", s))
  {
    sam.clear();
    for (int i = 0; s[i]; i++) sam.insert(s[i]);
    scanf("%s", s);
    sam.find(s);
  }
  return 0;
}