// 演算法：把 arr1 每個元素的「所有前綴」放進手寫雜湊表 S（開放定址 + 線性探測）。
// Algorithm: insert every prefix of every arr1[i] into a hand-rolled open-addressing
// hash table S. Then for each y in arr2, scan y's prefixes from longest to shortest
// (by repeatedly dividing by 10) and record the first hit's digit count.

#include <stdlib.h>   // calloc / free
#include <string.h>   // (not strictly needed but commonly included)

// 計算正整數 x 的位數 / count digits of positive integer x.
static int numDigits(int x) {
    int d = 0;                              // 累計位數 / digit counter
    while (x > 0) {                         // 還有位數沒砍完 / while digits remain
        d++;                                // 位數 +1 / increment count
        x /= 10;                            // 砍掉最右邊一位 / drop rightmost digit
    }
    return d;                               // 回傳位數 / return result
}

int longestCommonPrefix(int* arr1, int arr1Size, int* arr2, int arr2Size) {
    // 雜湊表槽位數選 2^20 ≈ 1,048,576，最多約 4.5×10^5 個鍵，負載因子 < 0.5。
    // Table size 2^20 keeps load factor < 0.5 for up to ~4.5×10^5 keys.
    const unsigned CAP = 1u << 20;          // 容量必須是 2 的次方 / capacity must be power of 2
    const unsigned MASK = CAP - 1;          // 用 & MASK 取餘（比 % 快）/ fast modulo via bitmask

    // calloc 把整塊記憶體歸零；因為題目保證輸入 ≥ 1，我們用 0 代表「空槽」。
    // calloc zeroes the memory; since all input values are ≥ 1, 0 safely means "empty slot".
    int *keys = (int*)calloc(CAP, sizeof(int));

    // -------- Step 1: 把 arr1 所有前綴塞進雜湊表 / insert all prefixes from arr1 --------
    for (int i = 0; i < arr1Size; i++) {    // 走訪 arr1 每個元素 / iterate arr1
        int x = arr1[i];                    // 取目前的數 / current value
        while (x > 0) {                     // 一直砍到變 0 / generate all prefixes
            // 用 Knuth's multiplicative hash：把 int 乘上一個質數常數，再取低位作為 index。
            // Knuth multiplicative hash: multiply by a large prime-ish constant and mask.
            unsigned h = ((unsigned)x * 2654435761u) & MASK;

            // 線性探測：若該槽已被別的 key 佔住，就往後一格找。
            // Linear probing: if occupied by a different key, step forward.
            while (keys[h] != 0 && keys[h] != x) {
                h = (h + 1) & MASK;          // 環狀往後 / wrap-around forward step
            }
            keys[h] = x;                    // 找到空槽或本身已存在，寫入即可 / write (idempotent)
            x /= 10;                        // 砍掉最右一位，產生下一個前綴 / next shorter prefix
        }
    }

    // -------- Step 2: 對 arr2 每個 y 找最長能命中 S 的前綴 / probe arr2 ---------------
    int best = 0;                           // 目前最佳答案 / best length so far
    for (int j = 0; j < arr2Size; j++) {    // 走訪 arr2 每個元素 / iterate arr2
        int y = arr2[j];                    // 從完整的 y 開始 / start from full y
        while (y > 0) {                     // 嘗試所有前綴（由長到短）/ longest → shortest
            unsigned h = ((unsigned)y * 2654435761u) & MASK;  // 同樣的雜湊函式 / same hash
            int found = 0;                  // 旗標：是否找到 / found flag
            while (keys[h] != 0) {          // 探測直到遇到空槽 / probe until empty
                if (keys[h] == y) { found = 1; break; }       // 命中！/ hit
                h = (h + 1) & MASK;          // 否則繼續往後 / otherwise keep probing
            }
            if (found) {                    // 第一次命中就是最長前綴 / first hit = longest
                int d = numDigits(y);       // 位數即答案候選 / digit count is the candidate
                if (d > best) best = d;     // 更新全域最佳 / update best
                break;                      // 不必再砍 y / done with this y
            }
            y /= 10;                        // 沒命中，砍一位再試 / try shorter prefix
        }
    }

    free(keys);                             // 釋放雜湊表記憶體 / release the table
    return best;                            // 回傳答案 / return result
}