Задача: даны две строки S и T. Нужно найти их общую подстроку наибольшей длины. По условиям обе строки имеют одинаковую длину L (1≤L≤100000) и состоят только из строчных латинских букв. Гарантируется, что строки имеют хотя бы одну общую букву.
Я решил следующим образом:
var s = Console.ReadLine();
var t = Console.ReadLine();
var best = string.Empty;
for (int start = 0; start < s.Length; start++)
for (int length = 1; start + length <= s.Length; length++)
{
var substring = s.Substring(start, length);
if (t.Contains(substring) && substring.Length > best.Length)
best = substring;
}
Console.WriteLine(best);
Но есть проблема - это неэффективно. Как можно сделать по-другому? Например, используя linq или же убрать один внешний цикл. Я плох в алгоритмах, а в гугле только такое решение.