最小表示法（字符串同构字典序最值）

original link - http://poj.org/problem?id1509题意求出一个字符串的循环同构中字典序最小的那个。解析假设定下两个指针i,ji,ji,j考虑比较这两个位置开始的字典序。往后延直到遇到一个不一样的字符然后比较这对字符的大小。假设中间走过kkk个相同的字符然后得出ilt;jilt;jij那么显然对于[i,ik][i,ik][i,ik]这些位置都在[j,jk][j,jk][j,jk]的位置存在更优解。所以我们让i→ik1i\to ik1i→ik1。同理igt;jigt;jij时跳转j→jk1j\to jk1j→jk1。由于两个指针都最多只跳转nnn次所以时间复杂度O(2n)O(2n)O(2n)。代码/* * Author : Jk_Chen * Date : 2019-09-01-09.34.36 */#includestdio.h#includemath.h#includeiostream#includealgorithm#includestring.husingnamespacestd;#defineLL long long#definerep(i,a,b) for(int i(int)(a);i(int)(b);i)#defineper(i,a,b) for(int i(int)(a);i(int)(b);i--)#definemmm(a,b) memset(a,b,sizeof(a))#definepb push_back#definepill pairint, int#definefi first#definese second#definedebug(x) cerr#x x\n;constLL mod1e97;constintmaxn1e49;LLrd(){LL ans0;charlast ,chgetchar();while(!(ch0ch9))lastch,chgetchar();while(ch0ch9)ansans*10ch-0,chgetchar();if(last-)ans-ans;returnans;}/*_________________________________________________________head*/charx[maxn];intmain(){inttrd();while(t--){gets(x);intlenstrlen(x);inti0,j1,k0;while(ilenjlenklen){intcmpx[(ik)%len]-x[(jk)%len];if(!cmp){k;}else{if(cmp0)ik1;elsejk1;if(ij)j;k0;}}intposmin(i,j);// 解的位置printf(%d\n,pos1);}return0;}