Rk算法for循环是两次，时间复杂度为何是n呢

[nmydt]

No description provided.

[nmydt]

	for(int i=0;i<=m-n;i++) {
		s=0;
        	    s+=(a1[i]-'a')*table[n]
		for(j=0;j<n;j++) {
			s+=(a1[i+j]-'a')*table[n-1-j];
		}
		hash[i]=s;
	}

[leonaron0410]

在 Rabin-Karp (RK) 字符串匹配算法中，时间复杂度的分析重点在于如何计算每一轮的哈希值。你给出的代码中有两层 for 循环，但其中的内层循环（第二个 for）在优化计算哈希值时可以被看作常数时间复杂度。
外层循环
外层 for 循环执行 m - n + 1 次，这里 m 是主串的长度，n 是模式串的长度，因此外层循环的次数大约是 O(m - n)，可以近似视为 O(m)。

内层循环的优化与哈希计算
在原始 Rabin-Karp 算法中，哈希值的计算可以通过一种称为 "滚动哈希" 的技巧来优化。在每一轮（每一个新的位置 i），不需要重新计算整个窗口的哈希值，而是根据上一次的哈希值进行增量更新（只需删除第一个字符，加上最后一个字符）。这种方法使得每次哈希更新的时间复杂度降为 O(1)。

但是在你提供的代码中，内层循环每次都会从头重新计算一遍哈希值，这样的时间复杂度确实会导致 O(m * n) 的复杂度。

如果使用滚动哈希技巧，内层循环 for (j = 0; j < n; j++) 可以在 O(1) 时间内完成每个新的哈希值更新。因此，优化后代码的时间复杂度是 O(m)，而不是 O(m * n)。

优化后的代码：
`import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String text = scanner.next();
String pattern = scanner.next();
int index = rabinKarp(text, pattern);
System.out.println("Pattern found at index: " + index);
scanner.close();
}

public static int rabinKarp(String text, String pattern) {
    int m = text.length();
    int n = pattern.length();
    int base = 26; // 基数，用于计算哈希值
    int prime = 101; // 一个大的质数，用于取模，防止溢出

    if (n > m) {
        return -1; // 如果模式串比主串长，直接返回-1
    }

    // 计算 pattern 和 text 第一个窗口的哈希值
    int patternHash = 0;
    int windowHash = 0;
    for (int i = 0; i < n; i++) {
        patternHash = (patternHash * base + (pattern.charAt(i) - 'a')) % prime;
        windowHash = (windowHash * base + (text.charAt(i) - 'a')) % prime;
    }

    // 滑动窗口进行匹配
    for (int i = 0; i <= m - n; i++) {
        // 如果哈希值相同，则进一步检查字符
        if (patternHash == windowHash) {
            boolean match = true;
            for (int j = 0; j < n; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return i; // 找到匹配
            }
        }

        // 计算下一个窗口的哈希值（滚动哈希）
        if (i < m - n) {
            windowHash = (windowHash - (text.charAt(i) - 'a') * pow(base, n - 1, prime)) % prime;
            windowHash = (windowHash * base + (text.charAt(i + n) - 'a')) % prime;

            // 如果哈希值是负数，转换为正数
            if (windowHash < 0) {
                windowHash += prime;
            }
        }
    }
    return -1; // 未找到匹配
}

// 计算 (base^exp) % prime
public static int pow(int base, int exp, int prime) {
    int result = 1;
    for (int i = 0; i < exp; i++) {
        result = (result * base) % prime;
    }
    return result;
}

}
`