一、KMP+最大最小值表示法
最大最小值表示法
最大最小表示法用于解决字符串的同构问题，其在复杂度为$ O(n) $的时间内求出一个字符串的所有同构串中字典序最大（小）的串的起始位置。
应用：
- 给出$ n $个循环字符串判断有多少不同字符串：逐个用最大（小）表示法表示，然后加入 (Set) 去重
- 循环字符串所有同构串中字典序最大（小）的表示：用最大（小）表示法求出起始位置，输出即可
- 判断两个字符串是否同构：将两字符串用最大（小）表示法表示，然后逐个字符比较
原理：
设一字符串 (S)，且 $S’ (是) S $的循环同构的串的最小表示，那么对于字符串循环同构的最小表示法，其问题实质是求 S 串的一个位置，从这个位置开始循环输出 (S)，得到的 $S’ $字典序最小。
最朴素的算法是设$ i(、)j (两个指针，)i (指向最小表示的位置，)j $作为比较指针。
令 (i=0)，(j=1)，那么：
- 若 (S[i]>S[j])，则：(i=j)，(j=i+1)
- 若 (S[i]<S[j])，则：(j++)
- 若 (S[i]=S[j])，则设指针 (k)，分别从 $i $和 $j (位置向下比较，直到) S[i]!=S[j]$
- 若 (S[i+k]>S[j+k])，则：(i=j)，(j=i+1)
- 否则$ j++$
最后返回 $i $即可
可以看出，朴素算法在 $S[i]=S[j] (时，)i $的指针移动的太少了，在遇到像 $bbb…bbbbbba $这样复杂的字符串时，时间复杂度可能会退化到 (O(n^2))，针对这一问题加以改进可得到 (O(n)) 的最小表示法的算法，其核心思路是在$ S[i]=S[j]$ 时同时维护 (i)、$j $两个指针
同样令 (i=0)，(j=1)，那么：
- 若 (S[i]>S[j])，则：(i=j)，(j=i+1)
- 若 (S[i]<S[j])，则：(j++)
- 若$ S[i]=S[j](，则设指针) k(，分别从) i (和) j $位置向下比较，直到 (S[i]!=S[j])
- 若 (S[i+k]>S[j+k])，则：(i=i+k)
- 否则 (j++)
最后返回$ i $和 $j $的小者即可
1、最小值表示法
int minmumRepresentation(char *str) //最小表示法
{
int len=strlen(str);
int i=0; //指向字符串最小的位置
int j=1; //比较指针
int k=0; //str[i]与str[j]相等时一次移动几个
while(i<len&&j<len&&k<len)
{
int temp=str[(i+k)%len]-str[(j+k)%len];//比较值的长度
if(temp==0)
k++;
else
{
if(temp>0) //维护i
i=i+k+1;
else //维护j
j=j+k+1;
if(i==j) //相等时比较指针后移
j++;
k=0;
}
}
return i<j?i:j; //返回i、j中较小的那个
}
2、最大值表示法
int maxmumRepresentation(char *str) //最大表示法
{
int len=strlen(str);
int i=0; //指向字符串最小的位置
int j=1; //比较指针
int k=0; //str[i]与str[j]相等时一次移动几个
while(i<len&&j<len&&k<len)
{
int temp=str[(i+k)%len]-str[(j+k)%len];//比较值的长度
if(temp==0)
k++;
else
{
if(temp>0) //维护i
j=j+k+1;
else //维护j
i=i+k+1;
if(i==j) //相等时比较指针后移
j++;
k=0;
}
}
return i<j?i:j; //返回两者最小值
}
HDU-3374解题思路
首先判定是否是循环串，然后用最小表示法和最大表示法来找出对应的位置，最小表示法可以找出比如一个环形的字符串，找出某个字符开始，然后这个字符串字典序最小
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define PI acos(-1.0)
#define E 1e-9
#define INF 0x3f3f3f3f
#define LL long long
const int MOD=10007;
const int N=1000000+5;
const int dx[]= {-1,1,0,0};
const int dy[]= {0,0,-1,1};
using namespace std;
int Next[N];
char str[N];
void getNext(char p[])
{
Next[0]=-1;
int len=strlen(p);
int j=0;
int k=-1;
while(j<len)
{
if(k==-1||p[j]==p[k])
{
k++;
j++;
Next[j]=k;
}
else
{
k=Next[k];
}
}
}
int minmumRepresentation(char *str) //最小表示法
{
int len=strlen(str);
int i=0;
int j=1;
int k=0;
while(i<len&&j<len&&k<len)
{
int temp=str[(i+k)%len]-str[(j+k)%len];
if(temp==0)
k++;
else
{
if(temp>0)
i=i+k+1;
else
j=j+k+1;
if(i==j)
j++;
k=0;
}
}
return i<j?i:j;
}
int maxmumRepresentation(char *str) //最大表示法
{
int len=strlen(str);
int i=0;
int j=1;
int k=0;
while(i<len&&j<len&&k<len)
{
int temp=str[(i+k)%len]-str[(j+k)%len];
if(temp==0)
k++;
else
{
if(temp>0)
j=j+k+1;
else
i=i+k+1;
if(i==j)
j++;
k=0;
}
}
return i<j?i:j;
}
int main()
{
while(scanf("%s",str)!=EOF)
{
getNext(str);
int n=strlen(str);
int len=n-Next[n];
int num=1;//数量
if(n%len==0)
num=n/len;
int minn=minmumRepresentation(str);//最小表示
int maxx=maxmumRepresentation(str);//最大表示
printf("%d %d %d %d
",minn+1,num,maxx+1,num);
}
return 0;
}