牛客网真题2019-27-字符串包含

本题是字符串匹配问题于是两种方法

• 按位匹配回溯
• kmp

import java.util.Scanner;

public class Main {
    public static int match(String s1, String s2){
        if(s1.length() < s2.length()){
            String temp = s2;
            s2 = s1;
            s1 = temp;
        }
        for(int i = 0; i < s1.length(); i++){
            if(s1.charAt(i) == s2.charAt(0)){
                for(int j = 0; j < s2.length(); j++){
                    if(i + j < s1.length() && s1.charAt(i + j) == s2.charAt(j)){
                        if(j == s2.length() - 1){
                            return 1;
                        }
                    }else{
                        break;
                    }
                }
            }
        }
        return 0;
    }


    /**
     * 求出一个字符数组的next数组
     *
     * @param t 字符数组
     * @return next数组
     */
    public static int[] getNextArray(char[] t){
        int[] next = new int[t.length];
        next[0] = -1;
        next[1] = 0;
        int k;
        for(int j = 2; j < t.length; j++){
            k = next[j - 1];
            while (k != -1) {
                if(t[j - 1] == t[k]){
                    next[j] = k + 1;
                    break;
                }else{
                    k = next[k];
                }
                next[j] = 0;  //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值
            }
        }
        return next;
    }

    /**
     * 对主串s和模式串t进行KMP模式匹配
     *
     * @param s 主串
     * @param t 模式串
     * @return 若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回-1
     */
    public static int kmpMatch(String s, String t){
        char[] s_arr = s.toCharArray();
        char[] t_arr = t.toCharArray();
        int[] next = getNextArray(t_arr);
        int i = 0, j = 0;//i，j分别是s和t的游标
        while (i < s_arr.length && j < t_arr.length) {
            if(j == -1 || s_arr[i] == t_arr[j]){
                i++;
                j++;
            }else
                j = next[j];
        }
        if(j == t_arr.length)
            return i - j;
        else
            return -1;
    }

    public static int kmp(String s1, String s2){
        if(s1.length() < s2.length()){
            String temp = s2;
            s2 = s1;
            s1 = temp;
        }
        if(kmpMatch(s1, s2) == -1){
            return 0;
        }else{
            return 1;
        }
    }


    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] s = sc.nextLine().split(" ");
            System.out.println(kmp(s[0], s[1]));
        }
    }
}