Basic String Questions

def str_str_naive(haystack, needle):
    n, m = len(haystack), len(needle)
    if m == 0: return 0
    for i in range(n - m + 1):
        if haystack[i:i+m] == needle:
            return i
    return -1

int strStr(string haystack, string needle) {
    int n = haystack.size(), m = needle.size();
    if (m == 0) return 0;
    vector<int> fail(m, 0);
    for (int k = 0, j = 1; j < m; j++) {
        while (k > 0 && needle[k] != needle[j]) k = fail[k - 1];
        if (needle[k] == needle[j]) k++;
        fail[j] = k;
    }
    for (int j = 0, i = 0; i < n; i++) {
        while (j > 0 && haystack[i] != needle[j]) j = fail[j - 1];
        if (haystack[i] == needle[j]) j++;
        if (j == m) return i - m + 1;
    }
    return -1;
}

def str_str(haystack, needle):
    n, m = len(haystack), len(needle)
    if m == 0: return 0
    fail = [0] * m
    k = 0
    for j in range(1, m):
        while k > 0 and needle[k] != needle[j]: k = fail[k - 1]
        if needle[k] == needle[j]: k += 1
        fail[j] = k
    j = 0
    for i in range(n):
        while j > 0 and haystack[i] != needle[j]: j = fail[j - 1]
        if haystack[i] == needle[j]: j += 1
        if j == m: return i - m + 1
    return -1

public int strStr(String haystack, String needle) {
    int n = haystack.length(), m = needle.length();
    if (m == 0) return 0;
    int[] fail = new int[m];
    for (int k = 0, j = 1; j < m; j++) {
        while (k > 0 && needle.charAt(k) != needle.charAt(j)) k = fail[k - 1];
        if (needle.charAt(k) == needle.charAt(j)) k++;
        fail[j] = k;
    }
    for (int j = 0, i = 0; i < n; i++) {
        while (j > 0 && haystack.charAt(i) != needle.charAt(j)) j = fail[j - 1];
        if (haystack.charAt(i) == needle.charAt(j)) j++;
        if (j == m) return i - m + 1;
    }
    return -1;
}

bool isAnagram(string s, string t) {
    if (s.size() != t.size()) return false;
    int freq[26] = {};
    for (char c : s) freq[c - 'a']++;
    for (char c : t) {
        if (--freq[c - 'a'] < 0) return false;
    }
    return true;
}

from collections import Counter
def is_anagram(s, t):
    return Counter(s) == Counter(t)

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    int[] freq = new int[26];
    for (char c : s.toCharArray()) freq[c - 'a']++;
    for (char c : t.toCharArray())
        if (--freq[c - 'a'] < 0) return false;
    return true;
}

def compress(chars):
    write = 0
    i = 0
    while i < len(chars):
        ch = chars[i]
        count = 0
        while i < len(chars) and chars[i] == ch:
            i += 1
            count += 1
        chars[write] = ch
        write += 1
        if count > 1:
            for digit in str(count):
                chars[write] = digit
                write += 1
    return write

string reverseWords(string s) {
    // Step 1: tokenize
    istringstream iss(s);
    vector<string> words;
    string w;
    while (iss >> w) words.push_back(w);
    // Step 2: reverse
    reverse(words.begin(), words.end());
    // Step 3: join
    string res;
    for (int i = 0; i < words.size(); i++) {
        if (i) res += ' ';
        res += words[i];
    }
    return res;
}

def reverse_words(s):
    return ' '.join(reversed(s.split()))

public String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");
    StringBuilder sb = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        if (sb.length() > 0) sb.append(' ');
        sb.append(words[i]);
    }
    return sb.toString();
}

string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty()) return "";
    for (int i = 0; i < strs[0].size(); i++) {
        char c = strs[0][i];
        for (auto& s : strs)
            if (i >= s.size() || s[i] != c)
                return strs[0].substr(0, i);
    }
    return strs[0];
}

def longest_common_prefix(strs):
    if not strs: return ""
    for i, chars in enumerate(zip(*strs)):
        if len(set(chars)) > 1:
            return strs[0][:i]
    return min(strs, key=len)

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    String prefix = strs[0];
    for (String s : strs) {
        while (!s.startsWith(prefix))
            prefix = prefix.substring(0, prefix.length() - 1);
    }
    return prefix;
}

def rolling_hashes(s, k, B=131, Q=10**9 + 7):
    n = len(s)
    if k > n: return []
    h = 0
    high = pow(B, k - 1, Q)
    for i in range(k):
        h = (h * B + ord(s[i])) % Q
    hashes = [h]
    for i in range(k, n):
        h = (h - ord(s[i - k]) * high) % Q
        h = (h * B + ord(s[i])) % Q
        hashes.append(h)
    return hashes