{"id":"c9826cad-573e-4e8b-88fc-a5528d1f6912","name":"String Rotation","description":"Three Programmers at Pepcoding invented an amusing game. First Pepcoder thought out a string S and passed it to the Second Pepcoder. The Second Pepcoder executed X (0< X < string length) cyclic shifts ( a cyclic shift is a transfer of the last character of the string to the beginning of this string) with this string. As a result of these operations, a string T was produced, and the Second Pepcoder passed it to the Third Pepcoder. The task of the Third Pepcoder was to find the number X or make sure that the Second Pepcoder was mistaken because the string T could not be produced from the string S via cyclic shifts.\r\n\r\nExpected complexity: O(n)","inputFormat":"The first line contains string S. The second line contains the string T.","outputFormat":"If the string T can be produced from the string S via cycle shifts you should output the desired number X, otherwise, you should output \"-1\". If multiple answers exist, output maximum X among them.","constraints":"1 &lt;= S.length() &lt;= 100000","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\tBufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n\t\tString S = br.readLine();\r\n\t\tString T = br.readLine();\r\n\r\n\t\tSolution(S, T);\r\n\t}\r\n\r\n\tprivate static void Solution(String s, String t) {\r\n\r\n\t}\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"pepcodingforlife\r\nforlifepepcoding","sampleOutput":"7\r\n","questionVideo":"https://www.youtube.com/embed/Z-lZrO6N6Ko","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"a2073e25-96a1-4875-b400-f40bbe2edd95","name":"Text Processing For Experts","slug":"text-processing-for-experts-859","type":0},{"id":"4db1ece4-b806-4cd6-bea3-c8b8a8e88932","name":"String Rotation","slug":"string-rotation","type":1}],"next":{"id":"7c79106b-4334-43bf-bc83-d1ae6f23d397","name":"Prefix And Suffix Count","type":1,"slug":"prefix-and-suffix-count"},"prev":{"id":"e5a74cfe-994f-4a66-9b70-d2a5c9de4df8","name":"Manacher's Algorithm","type":1,"slug":"manacher-s-algorithm"}}}

String Rotation

Three Programmers at Pepcoding invented an amusing game. First Pepcoder thought out a string S and passed it to the Second Pepcoder. The Second Pepcoder executed X (0< X < string length) cyclic shifts ( a cyclic shift is a transfer of the last character of the string to the beginning of this string) with this string. As a result of these operations, a string T was produced, and the Second Pepcoder passed it to the Third Pepcoder. The task of the Third Pepcoder was to find the number X or make sure that the Second Pepcoder was mistaken because the string T could not be produced from the string S via cyclic shifts. Expected complexity: O(n)

{"id":"c9826cad-573e-4e8b-88fc-a5528d1f6912","name":"String Rotation","description":"Three Programmers at Pepcoding invented an amusing game. First Pepcoder thought out a string S and passed it to the Second Pepcoder. The Second Pepcoder executed X (0< X < string length) cyclic shifts ( a cyclic shift is a transfer of the last character of the string to the beginning of this string) with this string. As a result of these operations, a string T was produced, and the Second Pepcoder passed it to the Third Pepcoder. The task of the Third Pepcoder was to find the number X or make sure that the Second Pepcoder was mistaken because the string T could not be produced from the string S via cyclic shifts.\r\n\r\nExpected complexity: O(n)","inputFormat":"The first line contains string S. The second line contains the string T.","outputFormat":"If the string T can be produced from the string S via cycle shifts you should output the desired number X, otherwise, you should output \"-1\". If multiple answers exist, output maximum X among them.","constraints":"1 &lt;= S.length() &lt;= 100000","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\tBufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n\t\tString S = br.readLine();\r\n\t\tString T = br.readLine();\r\n\r\n\t\tSolution(S, T);\r\n\t}\r\n\r\n\tprivate static void Solution(String s, String t) {\r\n\r\n\t}\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"pepcodingforlife\r\nforlifepepcoding","sampleOutput":"7\r\n","questionVideo":"https://www.youtube.com/embed/Z-lZrO6N6Ko","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"a2073e25-96a1-4875-b400-f40bbe2edd95","name":"Text Processing For Experts","slug":"text-processing-for-experts-859","type":0},{"id":"4db1ece4-b806-4cd6-bea3-c8b8a8e88932","name":"String Rotation","slug":"string-rotation","type":1}],"next":{"id":"7c79106b-4334-43bf-bc83-d1ae6f23d397","name":"Prefix And Suffix Count","type":1,"slug":"prefix-and-suffix-count"},"prev":{"id":"e5a74cfe-994f-4a66-9b70-d2a5c9de4df8","name":"Manacher's Algorithm","type":1,"slug":"manacher-s-algorithm"}}}
plane

Editor


Loading...

String Rotation

hard

Three Programmers at Pepcoding invented an amusing game. First Pepcoder thought out a string S and passed it to the Second Pepcoder. The Second Pepcoder executed X (0< X < string length) cyclic shifts ( a cyclic shift is a transfer of the last character of the string to the beginning of this string) with this string. As a result of these operations, a string T was produced, and the Second Pepcoder passed it to the Third Pepcoder. The task of the Third Pepcoder was to find the number X or make sure that the Second Pepcoder was mistaken because the string T could not be produced from the string S via cyclic shifts. Expected complexity: O(n)

Constraints

1 <= S.length() <= 100000

Format

Input

The first line contains string S. The second line contains the string T.

Output

If the string T can be produced from the string S via cycle shifts you should output the desired number X, otherwise, you should output "-1". If multiple answers exist, output maximum X among them.

Example

Sample Input

pepcodingforlife forlifepepcoding

Sample Output

7

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode