后缀自动机学习

深碍√TFBOYSˉ_ 2021-11-05 22:38 294阅读 0赞

1. [hihocoder \#1441 : 后缀自动机一·基本概念][hihocoder _1441 _]

按照后缀自动机概念模拟即可, 复杂度$O(n^3logn)$.

#include <iostream>
    #include <map>
    #include <string>
    #include <set>
    using namespace std;
    
    const int N = 111;
    int n, cnt;
    string s;
    map<string,set<int> > suf_to_endpos;
    map<set<int>,int> endpos_id;
    map<string,int> suf_id;
    set<string> st[N];
    string longest[N], shortest[N];
    set<int> endpos[N];
    
    int getID(set<int> &s) {
    	if (endpos_id.count(s)) return endpos_id[s];
    	endpos[++cnt] = s;
    	return endpos_id[s] = cnt;
    } 
    
    int main() {
    	cin>>s>>n;
    	for (int i=0; i<s.size(); ++i) {
    		for (int j=1; i+j<s.size(); ++j) {
    			suf_to_endpos[s.substr(i,j)].insert(i+j);
    		}
    	}
    	for (auto &t:suf_to_endpos) { 
    		int id = getID(t.second);
    		string suf = t.first;
    		st[id].insert(suf);
    		suf_id[suf] = id;
    		if (longest[id].empty()) longest[id] = shortest[id] = suf;
    		else {
    			if (suf.size()>longest[id].size()) longest[id] = suf;
    			if (suf.size()<shortest[id].size()) shortest[id] = suf;
    		}
    	}
    	while (n--) {
    		cin>>s;
    		int id = suf_id[s];
    		cout<<shortest[id]<<' '<<longest[id];
    		for (auto &&t:endpos[id]) cout<<' '<<t;
    		cout<<endl;
    	}
    }

2. [hihocoder \#1445 : 后缀自动机二·重复旋律5][hihocoder_1445 _ _5]

转载于:https://www.cnblogs.com/uid001/p/10953606.html

[hihocoder _1441 _]: http://hihocoder.com/problemset/problem/1441
[hihocoder_1445 _ _5]: http://hihocoder.com/problemset/problem/1445

发表评论取消回复

表情：

评论列表（有 0 条评论，294人围观）

还没有评论，来说两句吧...

相关阅读

相关后缀自动机(SAM) 合集

先上模板 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] int len[maxn << 1],fa[ma

落日映苍穹つ/ 2023年10月10日 07:51/ 0 赞/ 14 阅读

相关 POJ 3415 Common Substrings【后缀自动机】

max：即代码中 len 变量，它表示该状态能够接受的最长的字符串长度。 min：表示该状态能够接受的最短的字符串长度。实际上等于该状态的 fail 指针指向的结点的 le

拼搏现实的明天。/ 2022年08月08日 14:56/ 0 赞/ 133 阅读

相关【字符串新武器】后缀自动机

发链：[http://neroysq.blogcn.com/articles/%E5%90%8E%E7%BC%80%E8%87%AA%E5%8A%A8%E6%9C%BA%E5%

r囧r小猫/ 2022年08月05日 04:19/ 0 赞/ 185 阅读

相关后缀自动机详解

转载自：[点我][Link 1] 原论文（俄文）地址：[suffix\_automata][suffix_automata] 后缀自动机后缀自动机（单词的有向

川长思鸟来/ 2022年05月16日 08:20/ 0 赞/ 414 阅读

相关「bzoj3473 字符串」 - 后缀自动机

(好久没有更了,随便放一个) 题意给定 \\(n\\) 个字符串,询问每个字符串有多少子串（不包括空串）是所有 \\(n\\) 个字符串中至少 \\(k\\) 个字符

电玩女神/ 2022年01月07日 14:43/ 0 赞/ 221 阅读

相关后缀自动机之lcs

题意，给定两个字符串，求他们的最大的连续公共子串的长度是多少，数据范围是1--n 以前有一个DP思路，但是今天可以使用后缀自动机来写。首先对其中一个串a构造后缀自动机，然

Dear 丶/ 2021年11月19日 13:50/ 0 赞/ 331 阅读

相关 Substrings SPOJ - NSUBSTR （后缀自动机）

Substrings \\\[ Time Limit: 100ms\\quad Memory Limit: 1572864 kB \\\] 题意给出一个长度为

心已赠人/ 2021年11月09日 23:10/ 0 赞/ 285 阅读

相关后缀自动机学习

1. [hihocoder \1441 : 后缀自动机一·基本概念][hihocoder _1441 _] 按照后缀自动机概念模拟即可, 复杂度$O(n^3logn)$.

深碍√TFBOYSˉ_/ 2021年11月05日 22:38/ 0 赞/ 295 阅读

相关 SPOJ- Distinct Substrings(后缀数组&后缀自动机)

Given a string, we need to find the total number of its distinct substrings. Input T

一时失言乱红尘/ 2021年11月01日 05:30/ 0 赞/ 311 阅读

相关 BZOJ 3277/3473 广义后缀自动机

说实话没啥难的. 建一棵广义后缀自动机，暴力自底向上更新即可. 时间复杂度非常玄学，但据说是可以过的. 要注意每个串中相同的子串的贡献是都要加进去的，开始因为这个被坑了好

我会带着你远行/ 2021年09月30日 10:26/ 0 赞/ 312 阅读