给定一个s字符串和一个n字符串,在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1(需要给出多个测试用例,证明算法的正确性)。用java完成算法
时间: 2023-12-14 19:37:41 浏览: 42
好的,可以使用Java中的indexOf()方法来实现这个功能。具体实现代码如下:
```java
public class FindSubstring {
public static void main(String[] args) {
String s = "Hello World";
String n = "World";
int index = findSubstring(s, n);
System.out.println(index); // 输出 6
}
public static int findSubstring(String s, String n) {
return s.indexOf(n);
}
}
```
在这个示例中,我们输入了一个字符串s和一个子串n,然后调用了findSubstring()方法来查找n在s中出现的位置。如果找到了,就返回它的索引值,否则返回-1。
相关问题
给定一个s字符串和一个n字符串,在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1
好的,这个问题可以采用字符串匹配算法来解决,以下是一个基于暴力匹配的示例代码:
```
public static int findFirstAppearance(String s, String n) {
int slen = s.length();
int nlen = n.length();
if (slen < nlen) {
return -1;
}
for (int i = 0; i <= slen - nlen; i++) {
boolean flag = true;
for (int j = 0; j < nlen; j++) {
if (s.charAt(i + j) != n.charAt(j)) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return -1;
}
```
这个方法的时间复杂度为 O(m*n),其中m为s字符串的长度,n为n字符串的长度。如果需要更高效的实现,可以采用KMP、BM、Sunday等算法来优化。
算法分析给定一个s字符串和一个n字符串,在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在,则返回
这个问题可以使用经典的字符串匹配算法——KMP算法来解决。
KMP算法的核心思想是,当子串与主串不匹配时,不需要回溯主串的指针,而是利用已经匹配过的信息,将子串尽可能地往前移动一段距离,从而达到快速匹配的目的。
具体来说,KMP算法需要先对子串n进行预处理,得到一个next数组,其中next[i]表示当n的第i个字符与s不匹配时,n应该往后移动的位置。然后,我们用两个指针i和j分别遍历s和n,如果n[j]等于s[i],则i和j都往后移动一位;如果不匹配,我们利用next数组将j尽可能地往前移动,然后继续比较n[j]和s[i],直到找到匹配或者s遍历完毕。
具体实现可以参考以下代码:
```python
def kmp(s, n):
m, n = len(s), len(n)
if n == 0:
return 0
# 预处理next数组
next = [0] * n
j = 0
for i in range(1, n):
while j > 0 and n[i] != n[j]:
j = next[j-1]
if n[i] == n[j]:
j += 1
next[i] = j
# 匹配主串和子串
j = 0
for i in range(m):
while j > 0 and s[i] != n[j]:
j = next[j-1]
if s[i] == n[j]:
j += 1
if j == n:
return i - n + 1
return -1
```
其中,时间复杂度为O(m+n),其中m和n分别为s和n的长度。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)