广西大学东信杯 F.金手指
F金手指
最小字符串
- key：循环同构 ，最小字典序,
最小字典序的实现-----模式化
- 对比
- 拼接 -----发现一个新函数可用 s.substr（）；-----类似vb中的mid函数。
并且，对于string来说 可以直接进行< > =比较特别好用 拼接用+也方便！
关于k取值范围的问题：k<=n 最后一个位置,这里还有一个关键点，string分配是动态分配，所以即使是取到n的位置，也不会显示溢出。
当输入字符为aaaaaa时，此重复字符串，执行一次便跳出循环，此时k=n-1.
string minstring(string s){
int p1=0,p2=1,k; //开始的标记
int n=s.length(); //取长度
int site; //标记最小字典序开始的位置
while(p1s[p2+k]){
if(p1+k+1<=p2){ //注意这里是等号 因为即使相等 p1也要跑后面去不可能相同比较
p1=p2+1;
}else{
p1=p1+k+1;
}
}else if(s[p1+k] string minstring(string s){
int p0=0,p1=1,k;
int site，n=s.length();
while(p0s[p1+k])
if(p0+k+1<=p1) p0=p1+1;
else p0=p0+k+1;
else if(s[p0+k] string minstring(string s)
{
int p0=0,p1=1;
int site,n=s.length();
while(p0KMP----字符串模式匹配算法----关键字搜索
算法思想：模式串向右移动与主串进行比对，发现不同，为了节省时间，不直接将将模式串往后移一个位置，而是移动到在已匹配的字符中某个重复的最大字串位置
公式：T[i-ki-1]==P[0k-1]
遗留问题：取后面加前面为什么过不了 网上用的是两倍原字符串然后寻找关键字
巧妙：先找到每个位置的next（最大重复字符串指针的位置 便于副串的回溯）
有动态的思想了，顺着思路，若当前位置匹配，当然要匹配下一个位置了，下一个位置匹配，那么下一个位置的next应该和这个位置的next相同，若不匹配，就是目前的位置。若当前位置不匹配，那就从当前位置的上一个位置开始吧（上一个位置可能会经历过好几次不匹配，然后回到最初的起点。）。而k=-1就是为了如果回到最初开始服务的，并且最初的当前位置即j的next已经被赋值过了！可以看next[0]=-1。
这里k还有个很关键的点，在needle中表示的是位置信息，而赋值给next后表示的是与当前比较的j相同的位置的后一个位置！（即不匹配的第一个位置）
void getnext(string needle,int *next){
int next[0]=-1;//为什么为-1 首先
int k=-1;
int j=0;
while(j>a>>b;
int next[b.length()];
get_next(b,next);
cout<