怎么給網(wǎng)站做aapseo優(yōu)化專家
給你兩個(gè)字符串?haystack
?和?needle
?,請(qǐng)你在?haystack
?字符串中找出?needle
?字符串的第一個(gè)匹配項(xiàng)的下標(biāo)(下標(biāo)從 0 開始)。如果?needle
?不是?haystack
?的一部分,則返回??-1
?。
示例 1:
輸入:haystack = "sadbutsad", needle = "sad" 輸出:0 解釋:"sad" 在下標(biāo) 0 和 6 處匹配。 第一個(gè)匹配項(xiàng)的下標(biāo)是 0 ,所以返回 0 。
示例 2:
輸入:haystack = "leetcode", needle = "leeto" 輸出:-1 解釋:"leeto" 沒有在 "leetcode" 中出現(xiàn),所以返回 -1 。
public class title28 {public static void main(String[] args) {String haystack = "mississippi";String needle = "issip";int result = strStr(haystack, needle);System.out.println(result);}public static int strStr(String haystack, String needle) {int j = 0;int[] next;next=getNext(needle); //先算模式串的next[]//1.先判斷是否匹配,再找下標(biāo)//i指向母串,j指向模式串for (int i = 0; i < haystack.length(); i++) {//1.不匹配while (j>0 && haystack.charAt(i) != needle.charAt(j)) {j = next[j-1];}//2.字符匹配if (haystack.charAt(i) == needle.charAt(j)) {j++;}if(j==needle.length()){return i-needle.length()+1;}}return -1;}public static int[] getNext(String s){int j = 0;int[] next=new int[s.length()];next[0] = 0;for(int i = 1; i < s.length(); i++) { // 注意i從1開始,這樣才能和j比較while (j >0 && s.charAt(i) != s.charAt(j)) {// 處理前后綴不相同,回溯是個(gè)連續(xù)的過程,所以是while不是if,又因?yàn)閖起始位置是0,不能再回溯,所以是j>=0j = next[j-1]; // 向前回溯,回溯前一位的next中的位置}if (s.charAt(i) == s.charAt(j)){// 找到相同的前后綴j++; //最長相等前后綴長度加1}next[i] = j; // 將j(前綴的長度)賦給next[i],不管前后綴是否相同,都要存放}return next;}
}