字符串解析与匹配

def rabin_karp(text: str, pat: str) -> list[int]:
    """Start of every occurrence of a non-empty pat, found with rolling hashes."""
    MOD, BASE = 1_000_000_007, 131
    n, m = len(text), len(pat)
    if m > n:
        return []
    top = pow(BASE, m - 1, MOD)  # weight of the character leaving the window
    hp = hw = 0
    for i in range(m):
        hp = (hp * BASE + ord(pat[i])) % MOD
        hw = (hw * BASE + ord(text[i])) % MOD
    res = []
    for i in range(n - m + 1):
        if hw == hp and text[i : i + m] == pat:  # confirm a hit: hashes can collide
            res.append(i)
        if i + m < n:  # roll: drop text[i], add text[i + m]
            hw = ((hw - ord(text[i]) * top) * BASE + ord(text[i + m])) % MOD
    return res

// Start of every occurrence of a non-empty pat, found with rolling hashes.
vector<int> rabinKarp(const string& text, const string& pat) {
    const long long MOD = 1000000007, BASE = 131;
    int n = text.size(), m = pat.size();
    if (m > n) return {};
    long long top = 1, hp = 0, hw = 0;  // top: weight of the character leaving the window
    for (int i = 1; i < m; i++) top = top * BASE % MOD;
    for (int i = 0; i < m; i++) {
        hp = (hp * BASE + pat[i]) % MOD;
        hw = (hw * BASE + text[i]) % MOD;
    }
    vector<int> res;
    for (int i = 0; i + m <= n; i++) {
        if (hw == hp && text.compare(i, m, pat) == 0) res.push_back(i);  // confirm a hit: hashes can collide
        if (i + m < n)  // roll: drop text[i], add text[i + m]
            hw = ((hw - text[i] * top % MOD + MOD) % MOD * BASE + text[i + m]) % MOD;
    }
    return res;
}

class Solution {
    // Start of every occurrence of a non-empty pat, found with rolling hashes.
    List<Integer> rabinKarp(String text, String pat) {
        final long MOD = 1_000_000_007L, BASE = 131;
        int n = text.length(), m = pat.length();
        List<Integer> res = new ArrayList<>();
        if (m > n) return res;
        long top = 1, hp = 0, hw = 0; // top: weight of the character leaving the window
        for (int i = 1; i < m; i++) top = top * BASE % MOD;
        for (int i = 0; i < m; i++) {
            hp = (hp * BASE + pat.charAt(i)) % MOD;
            hw = (hw * BASE + text.charAt(i)) % MOD;
        }
        for (int i = 0; i + m <= n; i++) {
            if (hw == hp && text.startsWith(pat, i)) res.add(i); // confirm a hit: hashes can collide
            if (i + m < n) // roll: drop text[i], add text[i + m]
                hw = ((hw - text.charAt(i) * top % MOD + MOD) % MOD * BASE + text.charAt(i + m)) % MOD;
        }
        return res;
    }
}

// rabinKarp returns the start of every occurrence of a non-empty pat, found with rolling hashes.
func rabinKarp(text, pat string) []int {
	const mod, base = 1_000_000_007, 131
	n, m := len(text), len(pat)
	res := []int{}
	if m > n {
		return res
	}
	top, hp, hw := 1, 0, 0 // top: weight of the character leaving the window
	for i := 1; i < m; i++ {
		top = top * base % mod
	}
	for i := 0; i < m; i++ {
		hp = (hp*base + int(pat[i])) % mod
		hw = (hw*base + int(text[i])) % mod
	}
	for i := 0; i+m <= n; i++ {
		if hw == hp && text[i:i+m] == pat { // confirm a hit: hashes can collide
			res = append(res, i)
		}
		if i+m < n { // roll: drop text[i], add text[i + m]
			hw = ((hw-int(text[i])*top%mod+mod)%mod*base + int(text[i+m])) % mod
		}
	}
	return res
}

def reverse_words(s: str) -> str:
    """Words in reverse order, single spaces between them, none at the ends."""
    chars = list(s)

    def reverse(i: int, j: int) -> None:  # chars[i..j] in place
        while i < j:
            chars[i], chars[j] = chars[j], chars[i]
            i, j = i + 1, j - 1

    w = i = 0  # w writes, i reads; chars[:w] is the squeezed result so far
    while i < len(chars):
        if chars[i] == " ":
            i += 1
            continue
        if w:
            chars[w] = " "  # one space before every word but the first
            w += 1
        start = w
        while i < len(chars) and chars[i] != " ":
            chars[w] = chars[i]
            w, i = w + 1, i + 1
        reverse(start, w - 1)  # each word backwards now...
    reverse(0, w - 1)  # ...so reversing it all leaves the words in reverse order, each readable
    return "".join(chars[:w])

// Words in reverse order, single spaces between them, none at the ends.
string reverseWords(string s) {
    int w = 0;  // s[0, w) is the squeezed result so far
    for (int i = 0; i < (int)s.size();) {
        if (s[i] == ' ') {
            i++;
            continue;
        }
        if (w) s[w++] = ' ';  // one space before every word but the first
        int start = w;
        while (i < (int)s.size() && s[i] != ' ') s[w++] = s[i++];
        reverse(s.begin() + start, s.begin() + w);  // each word backwards now...
    }
    s.resize(w);
    reverse(s.begin(), s.end());  // ...so reversing it all leaves the words in reverse order, each readable
    return s;
}

class Solution {
    // Words in reverse order, single spaces between them, none at the ends.
    String reverseWords(String text) {
        char[] s = text.toCharArray();
        int w = 0; // s[0, w) is the squeezed result so far
        for (int i = 0; i < s.length;) {
            if (s[i] == ' ') {
                i++;
                continue;
            }
            if (w > 0) s[w++] = ' '; // one space before every word but the first
            int start = w;
            while (i < s.length && s[i] != ' ') s[w++] = s[i++];
            reverse(s, start, w - 1); // each word backwards now...
        }
        reverse(s, 0, w - 1); // ...so reversing it all leaves the words in reverse order, each readable
        return new String(s, 0, w);
    }

    private void reverse(char[] s, int i, int j) {
        for (; i < j; i++, j--) {
            char t = s[i];
            s[i] = s[j];
            s[j] = t;
        }
    }
}

// reverseWords returns the words in reverse order, single spaces between them, none at the ends.
func reverseWords(text string) string {
	s := []byte(text)
	reverse := func(i, j int) { // s[i..j] in place
		for ; i < j; i, j = i+1, j-1 {
			s[i], s[j] = s[j], s[i]
		}
	}
	w := 0 // s[:w] is the squeezed result so far
	for i := 0; i < len(s); {
		if s[i] == ' ' {
			i++
			continue
		}
		if w > 0 {
			s[w] = ' ' // one space before every word but the first
			w++
		}
		start := w
		for i < len(s) && s[i] != ' ' {
			s[w] = s[i]
			w, i = w+1, i+1
		}
		reverse(start, w-1) // each word backwards now...
	}
	reverse(0, w-1) // ...so reversing it all leaves the words in reverse order, each readable
	return string(s[:w])
}