java实现RKM匹配(附完整源码)
时间: 2023-11-09 16:07:43 浏览: 44
RKM算法是一种字符串匹配算法,它的时间复杂度为O(m+n),其中m为模式串的长度,n为文本串的长度。以下是Java实现RKM算法的完整源码:
```java
public class RKM {
/**
* RKM算法
*
* @param pattern 模式串
* @param text 文本串
* @return 匹配成功时返回第一次匹配的位置,否则返回-1
*/
public static int match(String pattern, String text) {
int m = pattern.length();
int n = text.length();
int d = 26; // 字符集大小
int q = 997; // 一个大质数,用于取模
// 计算模式串的哈希值
int p = 0;
for (int i = 0; i < m; i++) {
p = (d * p + pattern.charAt(i)) % q;
}
// 计算文本串中每个长度为m的子串的哈希值,并与模式串的哈希值比较
int t = 0;
for (int i = 0; i < m; i++) {
t = (d * t + text.charAt(i)) % q;
}
for (int i = 0; i <= n - m; i++) {
if (p == t && pattern.equals(text.substring(i, i + m))) {
return i;
}
if (i < n - m) {
t = (d * (t - text.charAt(i) * pow(d, m - 1)) + text.charAt(i + m)) % q;
if (t < 0) {
t += q;
}
}
}
return -1;
}
/**
* 计算x的n次幂
*/
private static int pow(int x, int n) {
int result = 1;
for (int i = 0; i < n; i++) {
result *= x;
}
return result;
}
public static void main(String[] args) {
String pattern = "abc";
String text = "abcbcabc";
int pos = match(pattern, text);
if (pos == -1) {
System.out.println("未找到匹配的子串");
} else {
System.out.println("子串\"" + pattern + "\"在文本串\"" + text + "\"中第一次出现的位置为:" + pos);
}
}
}
```
在主函数中,我们可以将模式串和文本串传递给match方法进行匹配。如果匹配成功,match方法将返回第一次匹配的位置,否则返回-1。在RKM算法中,我们需要选择一个大质数q,这个数通常选用1000000007或998244353等,以避免哈希值出现冲突。同时,我们需要选择一个较大的字符集大小d,这个数通常选用26或256等,以保证哈希值的分布均匀。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)