题意： 给定一个循环字符串，问字典序最小的串的开始位置。 思路： 之前用poj 1509 解题报告-字符串的最小表示法 A过 字符串的最小表示法的复杂度是O(n)，代码也不是很难写，不过由于最近在学SAM,所以用SAM写了一下。 参照张天扬的论文： 把原串复制一遍到后面，然后构建后缀自动机。 从初始状态开始，每次走字典序最小的转移，走|S|之后得到的就是最小循环表示。 如果求的是最小后缀，就在原串后加入一个比字符集中所有字符的字典序都小的字符作为终止后，再添加一遍原串。 /* *********************************************** Author :111qqz Created Time …

hdu 3374 题目链接 题意：给出一个循环字符串，问最小表示出现的位置以及次数，最大表示出现的位置以及次数。 思路：之前只写过最小表示。。最大表示其实是一样的。。。把不等式方向变号即可。。。对于出现的次数。。。其实就等同于这个字符串是由几个子串组成。。。跑一遍kmp。。答案为len-nxt[len]，1A /* *********************************************** Author :111qqz Created Time :2016年08月13日 星期六 03时22分47秒 File Name :code/hdu/3374.cpp …

hdu 2609 题目链接 题意：给出n个循环字符串，问有多少种。 思路：将每个字符串换成最小表示，然后set存一下即可。 /* *********************************************** Author :111qqz Created Time :2016年08月13日 星期六 02时44分21秒 File Name :code/hdu/2609.cpp ************************************************ */ #include <cstdio> #include <cstring> #include …

hdu 4162 题意：给出一串代表8个方向的数字，求这串序列的一阶差分（the first difference）的字典序最小的表示。 思路：先做个变换，按照题意，第i位的一阶差分 s[i] = ((s[i+1]-s[i])+8)%8; 然后求出最小表示开始的位置。。输出即可。 /* *********************************************** Author :111qqz Created Time :2016年08月13日 星期六 02时17分45秒 File Name :code/poj/4162.cpp …

poj 1509 题目链接 题意&思路：同uva 1314 /* *********************************************** Author :111qqz Created Time :2016年08月12日 星期五 18时48分29秒 File Name :code/uva/1314.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include …

uva 1314 题目链接 题意：给定一个循环字符串，问字典序最小的串的开始位置。最小表示法裸题。 /* *********************************************** Author :111qqz Created Time :2016年08月12日 星期五 18时48分29秒 File Name :code/uva/1314.cpp ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include …

首先放一波资料：叶子豪_最小表示法 周源_《浅谈最小表示法在字符串循环同构问题中的应用》 参考博客 对于字符串循环同构的最小表示法，其问题实质是求S串的一个位置，从这个位置开始循环输出S，得到的S’字典序最小。 一种朴素的方法是设计i,j两个指针。其中i指向最小表示的位置，j作为比较指针。 令i=0,j=1 如果S[i] S[j] i=j, j=i+1 如果S[i] S[j+k] i=j,j=i+1** _ 否则j++ **返回i** 注意到，朴素算法的缺陷在于斜体的情况下i指针的移动太少了。针对这一问题改进就得到了最小表示法的算法。最小表示法的算法思路是维护两个指针i,j。 令i=0,j=1 如果S[i] S[j] i=j, …