{"id":"94ee14fa-0705-4828-b6d0-feeaa11eff7f","name":"Repeated Substrings - Kattis","description":"https://open.kattis.com/problems/substrings","inputFormat":"Check link in description","outputFormat":"Check link in description","constraints":"Check link in description","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.*;\r\n\r\npublic class Main {\r\n static class SuffixArray {\r\n int MAX_N = 100010;\r\n int n = -1;\r\n String s;\r\n int[] RA = new int[MAX_N];\r\n int[] SA = new int[MAX_N];\r\n int[] tempRA = new int[MAX_N];\r\n int[] tempSA = new int[MAX_N];\r\n int[] lcp;\r\n\r\n void countingSort(int k) { // O(n)\r\n int i, maxi = Math.max(300, n); // up to 255 ASCII chars or length of n\r\n int sum = 0;\r\n int[] c = new int[MAX_N];\r\n // memset(c, 0, sizeof(c)); // clear frequency table\r\n for (i = 0; i < n; i++) c[i + k < n ? RA[i + k] : 0]++; // count the frequency of each integer rank\r\n\r\n for (i = 0; i < maxi; i++) {\r\n int t = c[i];\r\n c[i] = sum;\r\n sum += t;\r\n }\r\n\r\n for (i = 0; i < n; i++) // shuffle the suffix array if necessary\r\n tempSA[c[SA[i] + k < n ? RA[SA[i] + k] : 0]++] = SA[i];\r\n\r\n for (i = 0; i < n; i++) // update the suffix array SA\r\n SA[i] = tempSA[i];\r\n }\r\n\r\n SuffixArray(String x) {\r\n this.s = x;\r\n // this.s += \"$\";\r\n this.n = s.length();\r\n for (int i = 0; i < n; i++) RA[i] = s.charAt(i);\r\n for (int i = 0; i < n; i++) SA[i] = i;\r\n\r\n for (int k = 1; k < n; k *= 2) {\r\n countingSort(k);\r\n countingSort(0);\r\n\r\n int r = 0;\r\n tempRA[SA[0]] = r; // re-ranking; start from rank r = 0\r\n for (int i = 1; i < n; i++) // compare adjacent suffixes if same pair => same rank r; otherwise, increase r\r\n {\r\n tempRA[this.SA[i]] = (RA[this.SA[i]] == RA[this.SA[i - 1]] && RA[this.SA[i] + k] == RA[this.SA[i - 1] + k]) ? r : ++r;\r\n }\r\n\r\n for (int i = 0; i < n; i++) {\r\n RA[i] = tempRA[i]; // update the rank array RA\r\n }\r\n\r\n if (RA[this.SA[n - 1]] == n - 1)break; // nice optimization trick\r\n }\r\n kasai(); // use it to make lcp array in O(N) time\r\n }\r\n\r\n void kasai() {\r\n int k = 0;\r\n this.lcp = new int[n];\r\n int[] rank = new int[n];\r\n\r\n for (int i = 0; i < n; i++) rank[this.SA[i]] = i;\r\n\r\n for (int i = 0; i < n; i++, k = Math.max(k - 1, 0)) {\r\n if (rank[i] == n - 1) {\r\n k = 0;\r\n continue;\r\n }\r\n int j = this.SA[rank[i] + 1];\r\n while (i + k < n && j + k < n && s.charAt(i + k) == s.charAt(j + k)) k++;\r\n this.lcp[rank[i]] = k;\r\n }\r\n }\r\n }\r\n public static void printArray(int[] a, int n) {\r\n for (int i = 0; i < n; i++) {\r\n System.out.print(a[i] + \" \");\r\n }\r\n System.out.println();\r\n }\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n //Write code here, Suffix array has been implemented for you :)\r\n\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"3\r\naabaab\r\naaaaa\r\nAaAaA\r\n","sampleOutput":"5\r\n4\r\n5\r\n","questionVideo":"","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":"35641838-c371-46f9-b629-66e0cba928ac","name":"Repeated Substrings - Kattis","slug":"repeated-substrings-kattis","type":1}],"next":{"id":"c64a5455-09e9-4d26-9e4a-8a5eb00392fa","name":"Hidden Password - Icpc Regionals","type":1,"slug":"hidden-password-icpc-regionals"},"prev":{"id":"d224d03a-ccf3-4968-95a2-268c01dd4582","name":"Longest Common Substring (2 Strings)","type":1,"slug":"longest-common-substring-2-strings"}}}https://open.kattis.com/problems/substrings
{"id":"94ee14fa-0705-4828-b6d0-feeaa11eff7f","name":"Repeated Substrings - Kattis","description":"https://open.kattis.com/problems/substrings","inputFormat":"Check link in description","outputFormat":"Check link in description","constraints":"Check link in description","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.*;\r\n\r\npublic class Main {\r\n static class SuffixArray {\r\n int MAX_N = 100010;\r\n int n = -1;\r\n String s;\r\n int[] RA = new int[MAX_N];\r\n int[] SA = new int[MAX_N];\r\n int[] tempRA = new int[MAX_N];\r\n int[] tempSA = new int[MAX_N];\r\n int[] lcp;\r\n\r\n void countingSort(int k) { // O(n)\r\n int i, maxi = Math.max(300, n); // up to 255 ASCII chars or length of n\r\n int sum = 0;\r\n int[] c = new int[MAX_N];\r\n // memset(c, 0, sizeof(c)); // clear frequency table\r\n for (i = 0; i < n; i++) c[i + k < n ? RA[i + k] : 0]++; // count the frequency of each integer rank\r\n\r\n for (i = 0; i < maxi; i++) {\r\n int t = c[i];\r\n c[i] = sum;\r\n sum += t;\r\n }\r\n\r\n for (i = 0; i < n; i++) // shuffle the suffix array if necessary\r\n tempSA[c[SA[i] + k < n ? RA[SA[i] + k] : 0]++] = SA[i];\r\n\r\n for (i = 0; i < n; i++) // update the suffix array SA\r\n SA[i] = tempSA[i];\r\n }\r\n\r\n SuffixArray(String x) {\r\n this.s = x;\r\n // this.s += \"$\";\r\n this.n = s.length();\r\n for (int i = 0; i < n; i++) RA[i] = s.charAt(i);\r\n for (int i = 0; i < n; i++) SA[i] = i;\r\n\r\n for (int k = 1; k < n; k *= 2) {\r\n countingSort(k);\r\n countingSort(0);\r\n\r\n int r = 0;\r\n tempRA[SA[0]] = r; // re-ranking; start from rank r = 0\r\n for (int i = 1; i < n; i++) // compare adjacent suffixes if same pair => same rank r; otherwise, increase r\r\n {\r\n tempRA[this.SA[i]] = (RA[this.SA[i]] == RA[this.SA[i - 1]] && RA[this.SA[i] + k] == RA[this.SA[i - 1] + k]) ? r : ++r;\r\n }\r\n\r\n for (int i = 0; i < n; i++) {\r\n RA[i] = tempRA[i]; // update the rank array RA\r\n }\r\n\r\n if (RA[this.SA[n - 1]] == n - 1)break; // nice optimization trick\r\n }\r\n kasai(); // use it to make lcp array in O(N) time\r\n }\r\n\r\n void kasai() {\r\n int k = 0;\r\n this.lcp = new int[n];\r\n int[] rank = new int[n];\r\n\r\n for (int i = 0; i < n; i++) rank[this.SA[i]] = i;\r\n\r\n for (int i = 0; i < n; i++, k = Math.max(k - 1, 0)) {\r\n if (rank[i] == n - 1) {\r\n k = 0;\r\n continue;\r\n }\r\n int j = this.SA[rank[i] + 1];\r\n while (i + k < n && j + k < n && s.charAt(i + k) == s.charAt(j + k)) k++;\r\n this.lcp[rank[i]] = k;\r\n }\r\n }\r\n }\r\n public static void printArray(int[] a, int n) {\r\n for (int i = 0; i < n; i++) {\r\n System.out.print(a[i] + \" \");\r\n }\r\n System.out.println();\r\n }\r\n public static void main(String[] args) {\r\n Scanner scn = new Scanner(System.in);\r\n //Write code here, Suffix array has been implemented for you :)\r\n\r\n }\r\n}"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"3\r\naabaab\r\naaaaa\r\nAaAaA\r\n","sampleOutput":"5\r\n4\r\n5\r\n","questionVideo":"","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":"35641838-c371-46f9-b629-66e0cba928ac","name":"Repeated Substrings - Kattis","slug":"repeated-substrings-kattis","type":1}],"next":{"id":"c64a5455-09e9-4d26-9e4a-8a5eb00392fa","name":"Hidden Password - Icpc Regionals","type":1,"slug":"hidden-password-icpc-regionals"},"prev":{"id":"d224d03a-ccf3-4968-95a2-268c01dd4582","name":"Longest Common Substring (2 Strings)","type":1,"slug":"longest-common-substring-2-strings"}}}
Editor
Discussions
Show Discussion
Related Resources
