同 leetcode 28. 找出字符串中第一个匹配项的下标

题目描述

给你两个字符串t和p，要求从t中找到一个和p相同的连续子串，并输出该子串第一个字符的下标。

输入描述

• 输入文件包括两行 分别表示字符串t和p
• 保证t的长度不小于p
• 且t的长度不超过1000000
• p的长度不超过10000

输出描述

• 如果能从t中找到一个和p相等的连续子串，则输出该子串第一个字符在t中的下标，下标从左到右依次为1,2,3,…；
• 如果不能，则输出 “No”
• 如果含有多个这样的子串，则输出第一个字符下标最小的

用例1

输入

AVERDXIVYERDIAN
RDXI

输出

4

是KMP算法的经典应用，上一篇文章 【题解KMP-1】OD260. 最小循环子数组。 中详细介绍了模式串p的next[]数组（字符串【left=0，right=i】的最长公共前后缀子串长度）。

p匹配s的过程中，见下图s中子串abceabce匹配p中abceabcd，e和d的位置不匹配：

需要将模式串p中字符d之前的字符串abceabc的最长公共前后缀子串abc，用前缀公共字符串abc替换后缀公共字符串abc。

如果匹配，则j++。当j==p.length()的时候，模式串p到达完全匹配状态。

public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String t = br.readLine();
        String p = br.readLine();
        int[] next=KMPnext(p.toCharArray());
        int ans=kmp(t.toCharArray(),p.toCharArray(),next);
        System.out.println( ans==-1?"No":(ans+1));
    }

    public static int kmp(char[] str, char[] dest,int[] next){
        for(int i = 0, j = 0; i < str.length; i++){
		    //不匹配回退到最长公共前后缀结束的位置
            while(j > 0 && str[i]!= dest[j]) j = next[j - 1];
            if(str[i] == dest[j]) j++;
            if(j == dest.length) return i-j+1; //当j到达模式串结尾的时候，完全匹配模式串

        }
        return -1;
    }
	
	//生成next[] 数组
    public static int[] KMPnext(char[] dest){
        int[] next = new int[dest.length];
        for(int i = 1,j = 0; i < dest.length; i++){
            if(j > 0 && dest[j] != dest[i]) j = next[j - 1];
            if(dest[i] == dest[j]) j++;
            next[i] = j;
        }
        return next;
    }

同系列题目：

【题解KMP-1】OD260. 最小循环子数组

【题解KMP-2】OD267. 寻找相同子串