1、字符串匹配问题 给定一个s字符串和一个n字符串,在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1。java代码
时间: 2024-01-22 14:21:02 浏览: 53
java代码-使用java解决字符串前面或后面补零的源代码
可以使用 KMP 算法来解决字符串匹配问题。
KMP 算法的基本思想是,在匹配过程中,当发现不匹配的字符时,我们可以利用已经匹配成功的部分的信息,尽量减少模式串与主串的匹配次数。
具体实现可以先对模式串进行预处理,得到一个 next 数组,表示当匹配失败时,模式串需要跳到哪个位置继续匹配。然后在匹配过程中,根据 next 数组来调整模式串的位置。
以下是 Java 代码实现:
```
public class Solution {
public int strStr(String haystack, String needle) {
if (needle == null || needle.length() == 0) {
return 0;
}
int[] next = getNext(needle);
int i = 0, j = 0;
while (i < haystack.length() && j < needle.length()) {
if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == needle.length()) {
return i - j;
} else {
return -1;
}
}
private int[] getNext(String pattern) {
int[] next = new int[pattern.length()];
next[0] = -1;
int i = 0, j = -1;
while (i < pattern.length() - 1) {
if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
}
```
其中,getNext() 方法是用来预处理模式串的 next 数组的。
阅读全文