{"problem":{"name":"Prefix Concatenation","description":{"content":"You are given two strings $S$ and $T$ consisting of lowercase English letters. Find the minimum positive integer $k$ such that you can choose (not necessarily distinct) $k$ prefixes of $S$ so that the","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc257_g"},"statements":[{"statement_type":"Markdown","content":"You are given two strings $S$ and $T$ consisting of lowercase English letters.\nFind the minimum positive integer $k$ such that you can choose (not necessarily distinct) $k$ prefixes of $S$ so that their concatenation coincides with $T$.\nIn other words, find the minimum positive integer $k$ such that there exists a $k$\\-tuple $(a_1,a_2,\\ldots, a_k)$ of integers between $1$ and $|S|$ such that  \n$T=S_{a_1}+S_{a_2}+\\cdots +S_{a_k}$, where $S_i$ denotes the substring of $S$ from the $1$\\-st through the $i$\\-th characters and $+$ denotes the concatenation of strings.\nIf it is impossible to make it coincide with $T$, print $-1$ instead.\n\n## Constraints\n\n*   $1 \\leq |S| \\leq 5\\times 10^5$\n*   $1 \\leq |T| \\leq 5\\times 10^5$\n*   $S$ and $T$ are strings consisting of lowercase English letters.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$S$\n$T$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc257_g","tags":[],"sample_group":[["aba\nababaab","3\n\n$T=$ `ababaab` can be written as `ab` + `aba` + `ab`, of which `ab` and `aba` are prefixes of $S=$ `aba`.  \nSince it is unable to express `ababaab` with two or less prefixes of `aba`, print $3$."],["atcoder\nac","\\-1\n\nSince it is impossible to express $T$ as a concatenation of prefixes of $S$, print $-1$."]],"created_at":"2026-03-03 11:01:14"}}