Minimum Integer sequence
题意：
几行代码看了一个多小时！！吐血！！
明天再来补题~
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn=100010; 4 char s[maxn],t[maxn]; 5 int lens,lent; 6 int nex[maxn],ex[maxn]; 7 int best; 8 9 void getnex(char* t){ 10 nex[0]=lent; 11 int a=0,p=0; 12 for(int i=1;i<lent;i++){ 13 if(i>=p||i+nex[i-a]>=p){ 14 if(i>=p) p=i; 15 while(p<lent&&t[p]==t[p-i]) p++; 16 nex[i]=p-i; 17 a=i; 18 }else nex[i]=nex[i-a]; 19 } 20 } 21 void exkmp(char* s,char* t){ 22 getnex(t); 23 int a=0,p=0; 24 for(int i=0;i<lens;i++){ 25 if(i>=p||i+nex[i-a]>=p){ 26 if(i>=p) p=i; 27 while(p<lens&&p-i<lent&&s[p]==t[p-i]) p++; 28 ex[i]=p-i; 29 a=i; 30 }else ex[i]=nex[i-a]; 31 } 32 } 33 bool smaller(int x,int j){ 34 if(ex[j]+j<x) return s[j+ex[j]]<t[ex[j]]; 35 if(nex[x-j]+x-j<lent) return t[nex[x-j]]<t[x-j+nex[x-j]]; 36 if(nex[lent-(x-j)]<x-j) return t[lent-(x-j)+nex[lent-(x-j)]]<t[nex[lent-(x-j)]]; 37 return 0; 38 } 39 int main(){ 40 while(scanf("%s%s",s,t)!=EOF){ 41 lens=strlen(s);lent=strlen(t); 42 exkmp(s,t); 43 best=0; 44 for(int i=0;i<lens;i++){ 45 if(smaller(i+1,best)) best=i+1; 46 } 47 for(int i=0;i<best;i++) putchar(s[i]); 48 printf("%s",t); 49 printf("%s ",s+best); 50 } 51 return 0; 52 }
终于a掉了500题！！！
留念！！
update：2018-03-06
1 bool smaller(int x,int j){ 2 if(ex[j]+j<x) return s[j+ex[j]]<t[ex[j]]; //注释1 3 if(nex[x-j]+x-j<lent) return t[nex[x-j]]<t[x-j+nex[x-j]]; //注释2 4 if(nex[lent-(x-j)]<x-j) return t[lent-(x-j)+nex[lent-(x-j)]]<t[nex[lent-(x-j)]]; //注释3 5 return 0; //注释4 6 }
将B插入到A的x位置得到的数是否小于插入j位置？
分四种情况进行比较
注释1：最好理解的一种情况，从A的第j位开始，有ex[j]位和A的前ex[j]位相等， 到ex[j] + j位开始不等，而此时ex[j] + j仍小于新位置x。
注释2：
注释3：
注释4：位置x和位置j等价