{"id":"af10917e-b345-4312-9d4a-adfd046f52de","name":"Longest Common Substring (2 Strings)","description":"Given 2 strings, print the longest common substring.","inputFormat":"An integer N.\r\n2 strings S1, S1","outputFormat":"Print the longest common substring.","constraints":"|S1|,|S2| <= 10^5","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 {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 for (int i = 0; i < n; i++) {RA[i] = tempRA[i];} // update the rank array RA\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) {k=0; continue;}\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":"11\r\nyzpepcoding\r\ncodingpepcd\r\n","sampleOutput":"coding","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":"d224d03a-ccf3-4968-95a2-268c01dd4582","name":"Longest Common Substring (2 Strings)","slug":"longest-common-substring-2-strings","type":1}],"next":{"id":"35641838-c371-46f9-b629-66e0cba928ac","name":"Repeated Substrings - Kattis","type":1,"slug":"repeated-substrings-kattis"},"prev":{"id":"fa634ac6-6b8c-4c11-a927-ba7b57bdb42b","name":"Lexicographical Suffixes","type":1,"slug":"lexicographical-suffixes"}}}Given 2 strings, print the longest common substring.
{"id":"af10917e-b345-4312-9d4a-adfd046f52de","name":"Longest Common Substring (2 Strings)","description":"Given 2 strings, print the longest common substring.","inputFormat":"An integer N.\r\n2 strings S1, S1","outputFormat":"Print the longest common substring.","constraints":"|S1|,|S2| <= 10^5","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 {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 for (int i = 0; i < n; i++) {RA[i] = tempRA[i];} // update the rank array RA\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) {k=0; continue;}\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":"11\r\nyzpepcoding\r\ncodingpepcd\r\n","sampleOutput":"coding","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":"d224d03a-ccf3-4968-95a2-268c01dd4582","name":"Longest Common Substring (2 Strings)","slug":"longest-common-substring-2-strings","type":1}],"next":{"id":"35641838-c371-46f9-b629-66e0cba928ac","name":"Repeated Substrings - Kattis","type":1,"slug":"repeated-substrings-kattis"},"prev":{"id":"fa634ac6-6b8c-4c11-a927-ba7b57bdb42b","name":"Lexicographical Suffixes","type":1,"slug":"lexicographical-suffixes"}}}
Editor
Discussions
Show Discussion
Related Resources
