<commit_before>---
layout: post
title: SPOJ1811/LCS/Longest Common Substring
tags: [字符串,后缀自动机]
category: OI
---

<ruby>后缀自动机<rt>Suffix Automaton/SAM</rt></ruby>

将字符串A建立后缀自动机，用字符B在自动机上跑一遍，跑得最远的位置就是答案～

AC-Code

{% highlight cpp %}
/*
 * SPOJ 1811 LCS
 * Longest Common Substring
 * 后缀树/后缀自动机
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;<commit_msg>201405100951<commit_after>---
layout: post
title: SPOJ1811/LCS/Longest Common Substring
tags: [字符串,后缀自动机]
category: OI
---

<ruby>后缀自动机<rt>Suffix Automaton/SAM</rt></ruby>

将字符串A建立后缀自动机，用字符B在自动机上跑一遍，跑得最远的位置就是答案～

备注：此题卡$$O(n \log n)$$卡到丧心病狂！

AC-Code

{% highlight cpp %}
/*
 * SPOJ 1811 LCS
 * Longest Common Substring
 * 后缀树/后缀自动机
 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
{'fraction_non_alphanumeric': 0.14971428571428572, 'fraction_numerical': 0.032, 'mean_word_length': 5.257142857142857, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7566467', 'n_tokens_mistral': 464, 'n_tokens_neox': 475, 'n_words': 76}