字符串用s采用String对象存储,设计一个算法,在串s中查找子串t最后一次出现的位置,例如s=“abcdabcd”,t=“abc”,结果为4,采用BF算法求解,详细代码
时间: 2024-05-20 17:10:20 浏览: 74
以下是BF算法的详细代码实现(Java语言):
/**
* BF算法查找字符串s中最后一次出现子串t的位置
* @param s 原字符串
* @param t 子串
* @return 最后一次出现位置的索引,如果未找到则返回-1
*/
public static int lastIndex(String s, String t) {
int n = s.length();
int m = t.length();
if (m > n) {
return -1;
}
for (int i = n - m; i >= 0; i--) {
boolean match = true;
for (int j = 0; j < m; j++) {
if (s.charAt(i+j) != t.charAt(j)) {
match = false;
break;
}
}
if (match) {
return i;
}
}
return -1;
}
// 测试代码
public static void main(String[] args) {
String s = "abcdabcd";
String t = "abc";
int index = lastIndex(s, t);
System.out.println(index); // 输出4
}
注:BF算法的时间复杂度为O(n*m),其中n为主串长度,m为子串长度。虽然效率较低,但实现简单易懂,适用于数据规模较小的情况。
阅读全文