Problem: Longest common substring | Sololearn: Learn to code for FREE!
0

Problem: Longest common substring

I JUST WRITE THE ALGORITHM FOR THIS PROBLEM AND IT CRASHES AT THE LAST TEST. I’VE EVEN CONSIDERED THE CASE, WHERE THERE IS NO SUCH SUBSTRING HERE IS MY CODE: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace SoloLearn { class Program { static void Main(string[] args) { var words = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); var l = Longest(words[0], words[1]); //Console.WriteLine(string.Join(" ", l)); for(int i = 2; i < words.Length; i++) { l = l.Where(x => words[i].Contains(x)).ToList(); } //Console.WriteLine(string.Join(" ", l)); Console.WriteLine(l[l.Count - 1]); } static List<string> Longest(string s1, string s2) { int m = Math.Min(s1.Length, s2.Length); List<string> l = new List<string>(); l.Add(""); int maxLen = 0; for(int i = 0; i < s1.Length; i++) { for(int j = 0; j < s2.Length; j++) { if(s1[i] == s2[j]) { int k = -1; string s = ""; while(i + ++k < s1.Length && j + k < s2.Length && s1[i + k] == s2[j + k]) { s += s1[i + k]; } l.Add(s); } } } l = l.OrderBy(x => x.Length).ThenByDescending(x => x).ToList(); return l; } } }

22nd Jul 2020, 12:50 AM
Kristiyan Garchev
Kristiyan Garchev - avatar
3 ответов
+ 2
You already solved the task. Is this a new algorithm you created or were you finally able to find the problem in your code? If it's the latter, can you make public what went wrong so that beginners can learn from your mistake and thus give this question a meaning. If you have doubts with the code, let me know it and i'll give you some test cases where your code fails.
24th Jul 2020, 4:26 AM
Kevin ★
+ 1
the problem was at the Longest function: i had to add the string s to the list l inside the while loop. And at the end i switch l to be a hashset because the idea of adding s to l in the while loop would increase the size of l rapidly
24th Jul 2020, 10:38 AM
Kristiyan Garchev
Kristiyan Garchev - avatar
+ 1
// Hello where. Here is My version on C#. it pass all 6 tests: https://www.sololearn.com/ru/compiler-playground/c81zxq1Buzf4 using System; using System.Collections.Generic; using System.Linq; public class Program { public static void Main() { string[] words = Console.ReadLine().Split(' '); Array.Sort(words, (x, y) => x.Length.CompareTo(y.Length)); string word = words[0]; int length = word.Length; for (int i = length; i > 0; i--) { HashSet<string> substrings = new HashSet<string>(); for (int j = 0; j <= length - i; j++) { substrings.Add(word.Substring(j, i)); } List<string> ok = substrings.Where(ss => words.Skip(1).All(w => w.Contains(ss))).OrderBy(s => s).ToList(); if (ok.Any()) { Console.WriteLine(ok[0]); break; } } } }
8th Jan 2024, 2:35 PM
Игорь Акатов
Игорь Акатов - avatar