Вы можете сделать скользящее окно, хотя это меньше памяти, но требует больше времени.
Наименьшая подстрока - один символ (фактически, пустое слово - один, но давайте оставим это в стороне).
Возьмите символ 1 строки 1 и сохраните позиции этого символа в строке 2 в некоторой структуре данных, например на карте или в массиве.
Затем вы берете следующий (символ 2 изстрока 1) и сделайте то же самое.
Как только вы достигли конца строки 1, вы начинаете все сначала, но на этот раз вы берете каждые два символа строки 1 и всегда продвигаетесь на один символ, проверяя все позициив строке 2.
Вы делаете это до тех пор, пока длина проверяемой подстроки равна длине строки 1, что означает, что вы сравниваете строки 1 и 2 в целом.
Имейте в виду: если строка 2 длиннее строки 1, вам необходимо продвигать всю строку 1 один раз за каждый символ в строке 2, поскольку строка 1 может быть подстрокой строки 2.
Если строка 1 имеет значение larЕсли строка 2, вы можете прекратить проверку, как только ваша подстрока длиннее строки 2, все остальные подстроки будут проверены к тому времени.В идеале вы должны иметь карту (которая в простейшей форме представляет собой двумерный массив), которая содержит позиции каждой подстроки строки 1 в строке 2.