首页 > 【POJ1509】Glass Beads 【后缀自动机】

【POJ1509】Glass Beads 【后缀自动机】

题意

  给出一个字符串，求它的最小表示法。

分析

 这个题当然可以用最小表示法做啦！但是我是为了学后缀自动机鸭！

  我们把这个字符串长度乘二，然后建SAM，然后在SAM上每次跑最小的那个字母，找出长度为n的时候就停下。如果停下的那个状态时u，那么ans=st[u].len-n+1 

　　

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 
 7 using namespace std;
 8 const int maxn=20000+100;
 9 char s[maxn];
10 int n,T;
11 struct state{
12     map<char,int>next;
13     int len,link;
14 }st[4*maxn];
15 int last,cnt,cur;
16 void init(){
17     last=cur=0;
18     cnt=1;
19     st[0].len=0;
20     st[0].link=-1;
21     st[0].next.clear();
22 }
23 void build(char c){
24     cur=cnt++;
25     st[cur].next.clear();
26     st[cur].len=st[last].len+1;
27     int p;
28     for(p=last;p!=-1&&!st[p].next.count(c);p=st[p].link)
29         st[p].next[c]=cur;
30     if(p==-1)
31         st[cur].link=0;
32     else{
33         int q=st[p].next[c];
34         if(st[p].len+1==st[q].len)
35             st[cur].link=q;
36         else{
37             int clone=cnt++;
38             st[clone].next=st[q].next;
39             st[clone].link=st[q].link;
40             st[clone].len=st[p].len+1;
41             for(;p!=-1&&st  [p].next[c]==q;p=st[p].link)
42                 st[p].next[c]=clone;
43             st[q].link=clone;st[cur].link=clone;
44         }
45     }
46     last=cur;
47 }
48 int main(){
49     scanf("%d",&T);
50     for(int t=1;t<=T;t++){
51         scanf("%s",s);
52         n=strlen(s);
53         for(int i=0;i)
54             s[i+n]=s[i];
55         init();
56         for(int i=0;i)
57             build(s[i]);
58         for(int i=n;i<2*n;i++)
59             build(s[i]);
60         int u=0;
61         for(int i=0;i){
62             for(int j='a';j<='z';j++){
63                 if(st[u].next.count(j)){
64                     u=st[u].next[j];
65                     break;
66                 }
67             }
68         }
69         int ans=st[u].len-n+1;
70         printf("%d
",ans);
71     }
72 return 0;
73 }
View Code

 

转载于:https://www.cnblogs.com/LQLlulu/p/9882133.html

更多相关：

  • [转]解析字符串的方法

    解析字符串的方法 char st[]=”123.45ab”; 解析这一段字符串，有很多种方法。这里介绍一个在”stdio.h”里面的函数: sscanf(…); 如果你看了如下代码，应该会有所感悟： 1 # include "stdio.h"2 3 int main() {4 char st[]="123.45...

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • 二维指针操作链表

    背景 Linus slashdot:    https://meta.slashdot.org/story/12/10/11/0030249 Linus大婶在slashdot上回答一些编程爱好者的提问，其中一个人问他什么样的代码是他所喜好的，大婶表述了自己一些观点之后，举了一个指针的例子，解释了什么才是core low-level...

  • leetcode-386 字典序排数

    给定一个整数 n, 返回从 1 到 n 的字典顺序。 例如， 给定 n =13，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。 请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。 根据题目描述，所谓字典顺序，即数值按照类似字符串首字母的ASCII大小进行排序...

  • 二叉树 2.0 -- 非递归遍历

    二叉树递归遍历存在的问题 如果我们的二叉树只有左子树，而且树的高度还很深的时候，这个时候递归调用遍历的时候，栈帧空间开辟的较大，很可能造成栈溢出。但是我们一个程序中，为堆分配的空间要比栈大的多，这个时候我们可以实现一个二叉树遍历的非递归的实现形式，模拟栈帧调用的过程，自己模拟一个栈用于保存节点，然后实现遍历。 非递归实现树的遍历...

  • BZOJ 3085: 反质数加强版SAPGAP （反素数搜索）

    题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3085 题意：求n(<=10^100)之内最大的反素数。 思路： 优化2：   int prime[]= {1, 2, 3, 5, 7,11, 13, 17, 19, 23,29, 31, 37, 41,...

  • HDU 4832 Chess 排列组合 DP

    Chess Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 351    Accepted Submission(s): 124 Problem Description 小度和...

©2024 11GX.COM