package com.model.string;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.HashMap;

/**
 * @Description:测试类
 * @Author: 张紫韩
 * @Crete 2021/8/31 23:11
 * 给你两个字符串，找到同源异构字符串
 * acbd 和abc 即 acb为abc的同源异构字符串
 */
public class StringDemo01 {
    public static void main(String[] args) {
        String str1="fasdfsdabcdefg";
        String str2="bca";
        System.out.println(getIndex(str1, str2));

        System.out.println(getIndex2(str1, str2));
    }

//    窗口移动+记账法
    public static int getIndex2(String str1,String str2){

        if (str1.length()<str2.length()||str2.length()==0){
            return -1;
        }
        int[] table=new int[256];
//        无效还款数
        int invalid=0;
//        形成账单
        for (int i = 0; i < str2.length(); i++) {
           table[str2.charAt(i)]++;
        }
//        先行成第一个窗口
        for (int i = 0; i < str2.length(); i++) {
            if (table[str1.charAt(i)]==0){
                invalid++;
            }
            table[str1.charAt(i)]--;
        }
        if (invalid==0){
            return 0;
        }

        for (int i = 0;i < str1.length()-str2.length()+1; i++) {
//           判断是否已经全部还款，且无效还款为0
            if (invalid==0){
                return i;
            }
//            滑动窗口
            if (table[str1.charAt(i)]++<0){
                invalid--;
            }
            if (table[str1.charAt(i+str2.length())]--==0){
                invalid++;
            }
        }

        return -1;
    }



    //普通方法，列举出所有的和str2一样长的字串进行比对
    public static int getIndex(String str1,String str2){
        for (int i = 0; i < str1.length()-str2.length()+1; i++) {
            if (isTY(str1.substring(i, i+str2.length()), str2)){
                return i;
            }
        }
        return -1;
    }
//    判断两个字符串是否是同源字符串
    public static boolean isTY(String str1,String str2){
        int[] table=new int[256];
        for (int i = 0; i < str2.length(); i++) {
            table[str2.charAt(i)]++;
        }
        for (int i = 0; i < str1.length(); i++) {
            if (table[str1.charAt(i)]==0){
                return false;
            }
            table[str1.charAt(i)]--;
        }
        return true;
    }
}