{"id":"03793180-8e17-49d1-9b73-2f4941a03848","name":"Prefix And Suffix Count","description":"Given a string s, Your task is, for any prefix of string s which matches a suffix of string s, print the number of times it occurs in string s as a substring.\r\nExpected Complexity: O(n)","inputFormat":"The first line contains string s.","outputFormat":"In the first line, print integer k (0<=k<=|s|) - the number of prefixes that match a suffix of string s. Next print k lines, in each line print two integers li ci. Numbers li ci mean that the prefix of the length li matches the suffix of length li and occurs in string s as a substring ci times. Print pairs li ci in the order of increasing li.","constraints":"1<= s.length() <= 10^5","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.BufferedReader;\r\nimport java.io.IOException;\r\nimport java.io.InputStreamReader;\r\n\r\npublic class Main {\r\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\t\r\n\t}\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"ABABABAB","sampleOutput":"4\r\n2 4\r\n4 3\r\n6 2\r\n8 1","questionVideo":"https://www.youtube.com/embed/-g2keRF4E4k","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":"7c79106b-4334-43bf-bc83-d1ae6f23d397","name":"Prefix And Suffix Count","slug":"prefix-and-suffix-count","type":1}],"next":{"id":"69b9695f-ba89-4aca-ace1-4ca7dbbf5c38","name":"Say No To Palindrome","type":1,"slug":"say-no-to-palindrome"},"prev":{"id":"4db1ece4-b806-4cd6-bea3-c8b8a8e88932","name":"String Rotation","type":1,"slug":"string-rotation"}}}Given a string s, Your task is, for any prefix of string s which matches a suffix of string s, print the number of times it occurs in string s as a substring. Expected Complexity: O(n)
{"id":"03793180-8e17-49d1-9b73-2f4941a03848","name":"Prefix And Suffix Count","description":"Given a string s, Your task is, for any prefix of string s which matches a suffix of string s, print the number of times it occurs in string s as a substring.\r\nExpected Complexity: O(n)","inputFormat":"The first line contains string s.","outputFormat":"In the first line, print integer k (0<=k<=|s|) - the number of prefixes that match a suffix of string s. Next print k lines, in each line print two integers li ci. Numbers li ci mean that the prefix of the length li matches the suffix of length li and occurs in string s as a substring ci times. Print pairs li ci in the order of increasing li.","constraints":"1<= s.length() <= 10^5","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.BufferedReader;\r\nimport java.io.IOException;\r\nimport java.io.InputStreamReader;\r\n\r\npublic class Main {\r\n\tpublic static void main(String[] args) throws NumberFormatException, IOException {\r\n\t\t\r\n\t}\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"ABABABAB","sampleOutput":"4\r\n2 4\r\n4 3\r\n6 2\r\n8 1","questionVideo":"https://www.youtube.com/embed/-g2keRF4E4k","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":"7c79106b-4334-43bf-bc83-d1ae6f23d397","name":"Prefix And Suffix Count","slug":"prefix-and-suffix-count","type":1}],"next":{"id":"69b9695f-ba89-4aca-ace1-4ca7dbbf5c38","name":"Say No To Palindrome","type":1,"slug":"say-no-to-palindrome"},"prev":{"id":"4db1ece4-b806-4cd6-bea3-c8b8a8e88932","name":"String Rotation","type":1,"slug":"string-rotation"}}}
Editor
Discussions
Show Discussion
Related Resources
