尺取法应用题hiho字符串
如果一个字符串恰好包含2个'h',1个‘1’和1个‘0’，我们就称这个字符串是hiho字符串
例如"oihateher"、“hugeinputhugeoutput”都是hiho字符串
现在给定一个只包含小写字母的字符串S，小H想知道S的所有子串中，最短的hiho字符串是哪个
punlic static void solve2(char[] w){
int min=Integer.MAX_VLUE;
int j=-1;
for(int i-=0;i<w.length;i++)
{
char c=w[i];
if(check(c)){//i停下
if(j==-1){//j的第一次定位
j=i+1;
}
while(j<w.length){
char c2=w[j];
if(check(c2)&&containsAll(w,i,j)){//c2是否为关键字，且全部囊括2个h，1个i,1个o
if(check(w,i,j)&&j-i+1<min)//恰好包含，且更新min
min=j-i+1;
}
break;//j停下
}
j++;//j继续扫描
}
}
System.out.println(min==Integer.MAX_VALUE?-1:min);
}
//检查字符序列是否恰好包含2个h一个i和一个o
private static boolean check(char[] w,int i,int j){
int c1=0,c2=0.c3=0;
for(int k=i;k<=j;j++){
if(w[k]=='h')c1++;
if(w[k]=='i')c2++;
if(w[k]=='o')c3++;
}
return c1==2&&c2==1&&c3==1;
}
private static boolean check(char c){
return c=='h'||c=='i'||c=='o';
}
private static boolean containsAll(char[] w.int i,int j) {
int c1=0;c2=0,c3=0;
for(int k=i;k<=j;k++){
if(w[k]=='h')c1++;
if(w[k]=='i')c2++;
if(w[k]=='o')c3++;
}
return c1>=2&&c2>=1&&c3>=1;
}
next数组应用前缀周期性
前缀是否为周期性的，如果是周期性的，输出前缀的下标和周期重复次数
3
aaa
12
aabaabaabaab
0
2 2
3 3
2 2
6 2
9 3
12 4
next[j]=k;
k%(j-k)=0则证明串为周期性的
j/(j-k)则是循环的次数
public static void main(){
Scanner sc=new Scanner(System.in);
List<String> list =new ArrayList<String>();//定义一个线性表
int caseNum=1;
while(true){
int n=sc.next();//输入字符串的数量
if(n==0){
break;
}
String s=sc.next();//输入字符串
list.add(s);//将字符串加入线性表
}
for(int j=0;j<list.size();j++){
String s=list.get(j);//拿出一个字符串
//int len=s.length();
int[] next=next(s);
System.out.println("Test case #"+(j+1));
boolean flag=false;
for(int i=2;i<next.length;i++){//挨个依次遍历，找next看是否满足(j-k)%k=0
int k=next[i];//找next
int t=i-k;
if(i%t==0&&i/t>1){//若是k等于0，，i%(i-k)同样等于0，所以还要满足i/t>1
System.out.println(i+" "+i/t);//i/(i-k)为循环体的次数
}
}
System.out.println();
}
}
后缀数组的应用
后缀数组+高度数组
-最长重复子串（可重复或者说可交叉）
-不可重复的最长重复子串
-可重叠并且出现至少k次的最长子串
-最长重复子串（可重复或者说可交叉）
112323232345
2323232345
23232345------->6
两个后缀的前缀相同，这个叫做重复
public static int maxRepeatSubString(String src){
Match03_SuffixArray.suff[] sa=Match03_suffixArray.getSa2(src);
int[] height =Match03_SuffixArray.getHeight(src,sa);
int maxHeight=0;
int maxIndex=-1;
for(int i=0;i<height.length;i++){
if(height[i]>maxHeight){
maxHeight=height[i];
maxIndex=i;
}
}
int index=sa[maxindex].index;//转成原始下标
Syste.out.println(src.substring(index,index+maxHeight));
return maxHeight;
}
-不可重复的最长重复子串
//二分枚举+height分组
最大高度的两个字符串在后缀数组中的原始下标，且两个下标之差，大于等于两个字符串的最大公共前缀
//用length将height分组，小于组和大于等于组交替
//在大于组中更新最大最小原始下标，大转小的时候检查上一个大于组是否满足不重叠
//在小于族中，只需持续地将原始下标赋给max和min，这样小转大的时候，可以保留小于组最后一个元素地小标
public static boolean check(int[] height,Match03_SuffixArray,Suff[] sa,int len){
int minIndex=sa[0].index;
int minIndex=sa[0].index;//maxIndex:5
for(int i=1;i<height.length;i++){//i:5
int index=sa[i].index;//index:8 sa:Match03_SuffixArraySuff[9] 613
if(height[i]>=len){//lcp大于len height:{0 0 2 4 6 0 1 3 5} i: 5
minIndex=min(minIndex,index);//小转大
maxIndex=max(maxIndex,index);
}else{//大转小
if(maxIndex-minIndex>=len){//maxIndex:5 minIndex:1 len:4
return true;
}
maxIndex=index;
minIndex=index;
}
}
}
public static int maxRepeatSubString2(String src){
Match03_SuffArray.Suff[] sa=Match03_SuffixArray.getSa2(src);
int l=0;
int r=height.length;
int ans=0;
while(l<=r){
int mid=l+((r-l)>>1);//chech的重叠长度
if(check(height,sa,mid)){
if(mid=height.length/2){
return mid;
}
l=mid+1;
ans=mid;
}else{
r=mid-1;
}
}
return ans;
}
public static int maxRepeatSubString(String src){
Match03_SuffixArray.suff[] sa=Match03_suffixArray.getSa2(src);
int[] height =Match03_SuffixArray.getHeight(src,sa);
int maxHeight=0;
int maxIndex=-1;
for(int i=0;i<height.length;i++){
if(height[i]>maxHeight){
int index=sa[i].index;//转成原始下标
int index1=sa[i-1].index;//转成原始下标
if(Math.abs(index-index1)>=height[i]){
maxHeight=height[i];
maxIndex=i;
}
}
}
int index=sa[maxindex].index;//转成原始下标
Syste.out.println(src.substring(index,index+maxHeight));
return maxHeight;
}
本文含有隐藏内容，请 开通VIP 后查看