suffix automaton by words
Project description
SuffixAutomaton 后缀自动机
suffix automaton by words
usage
pip install SuffixAutomaton
raw = """
ASE : International Conference on Automated Software Engineering
ESEC/FSE : ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering
ICSE : International Conference on Software Engineering
ISSTA : The International Symposium on Software Testing and Analysis
"""
doc = raw.splitlines()
doc = [x for x in doc if x]
doc = [x.split() for x in doc]
# tokenize in words
from SuffixAutomaton import SuffixAutomaton,lcs1,lcs2
# longest
print(lcs1(doc[1], doc[2])) # [(['Software', 'Engineering'], 14)]
print(lcs2(doc[0], doc[1:4])) # [([':'], 1), (['on'], 4), (['Software'], 6)]
poet = "江天一色无纤尘皎皎空中孤月轮 江畔何人初见月江月何年初照人 人生代代无穷已江月年年望相似 不知江月待何人但见长江送流水"
doc = poet.split()
# tokenize in chars
# all common substrings
# [(['人'], 13), (['江'], 0), (['江', '月'], 7), (['年'], 10)]
print(lcs1(doc[1], doc[2], 1))
# [(['人'], 0), (['江', '月'], 7)]
print(lcs2(doc[2], doc[2:4], 1))
feature
- suffix automaton [in words] 可分词后缀自动机
- [Longest] Common Substring of two lines 两文[最长]共串
- [Longest] Common Substring of document 多文[最长]共串
inspired by
参照:https://www.cnblogs.com/shld/p/10444808.html
讲解:https://www.cnblogs.com/zjp-shadow/p/9218214.html
详解:https://www.cnblogs.com/1625--H/p/12416198.html
证明:https://oi-wiki.org/string/sam/
题解:https://www.cnblogs.com/Lyush/archive/2013/08/25/3281546.html https://www.cnblogs.com/mollnn/p/13175736.html
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
SuffixAutomaton-0.0.1.tar.gz
(5.4 kB
view hashes)
Built Distribution
Close
Hashes for SuffixAutomaton-0.0.1-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f609754e37ca9f28614314b6ef820d7f582533a64e857e8578c40fae9f38ccac |
|
MD5 | 8a767178e3fd47243fd210481b33b021 |
|
BLAKE2b-256 | 9ff96e67abafaf5cac32fd04fe2d0c844a9eb1d69c76665be517bced27ecb855 |